Public
Edited
Feb 26, 2021
function reduceState(state) {
//state[0] = state[0].filter(e => e !== 3)
return undefined;
}
function solveSquare(perm) { // solve for square problem: forall x : nat, f(f(x)) = perm
const n = perm.length;
let state = new Array(n).fill(undefined);
let digitsSet = new Set(); // digits that in left part of state
let solutions = [];
// Check wrong inputs
checkInput(perm);
// Recursive helper
//solve(state, 0);
// 0000, 0001, 0002, 0003, 0010, ...
function checkState(state) {
digitsSet.add(state)
return isEqual(compose(state, state), perm);
}
function solve(state, index = 0) {
if (index >= n) {
if (checkState(state)) {
solutions.push(copyArray(state));
}
return;
}
for (let i = 0; i < n; i++) {
state[index] = i;
solve(state, index + 1);
}
}
return solutions;
}
solvePermutation(permSquare([0,1,2,3,6,5,7,4])).solutions
permSquare = p => compose(p, p)
showSolutions(solveSquareBruteForce([1,0,3,2]).solutions)
examples = [
firstExample,
secondExample
]
solutionsFirstExample = solveSquareBruteForce(examples[0]).solutions
md`### Ideas:
\`\`\`text
I1: f^2 = [0,2,4,6,4,2,0] => f = [0,*,*,*,4,*,*] || [4,*,*,*,0,*,*]
1) explore equations like f^2 = [0,*,2,*] and find possible counterexamples.
2) "counterexample": f^2 = [0, 1, 2, 3] have [1, 0, 2, 3] solution => it's not a really counterexample because f(3) = 3
3) formulation of I1: We can swap in state of solutions only fixed points like f(i) = i
\`\`\`
### Lemmas:
\`\`\`
L1: ---
\`\`\`
`
s1 = solveSquareBruteForce([0,2,4,6,4,2,0]).solutions
7**7
s2 = {
const c = 5; // we made class of 0 and 4: c = {0, 4}
return solveSquareBruteForce([1, c, 4, 1, c, c]).solutions;
}
{
// [4, 3, 6, 2, 0, 3, 4]
// [4, 6, 0, 1, 0, 6, 2]
// [4, 6, 0, 5, 0, 6, 2]
// [2, 4, 1, 2, C, C]
// [4, C, 0, 4, 1, C]
// [4, C, 3, 4, 1, C]
let C = 5;
let map = {0: 'c', 4: 'c', 3: 2, 6: 4, 2: 1, 1: 0, 5: 3};
return s1.map(sol => sol.map(i => map[i]));
}
(p => ({input: p, square: permSquare(p), solutions: solveSquareBruteForce(permSquare(p)).solutions}))([2, 0, 1]) // Example of one solution
(p => ({input: p, square: permSquare(p), solutions: solveSquareBruteForce(permSquare(p)).solutions}))([0, 3, 1, 2]) // isomorphic example to last one [1] ++ [2, 0, 1] + 1 = [1] ++ [3, 1, 2] = [1, 3, 1, 2]
permSquare([0, 3, 6, 2, 1, 3, 4]) // another example that have one solution: [0, 3, 6, 2, 1, 3, 4]
function solveOLD(p, n) { // for demonstration how to use error.notImplemented(message)
if (isEqual(p, examples[0])) {
return [[1, 3, 0, 2], [2, 0, 3, 1]];
} else {
error.notImplemented("solve function");
return [];
}
}
function checkIsSquareOf(p, squareP) {
assert(isEqual(compose(p, p), squareP));
return p;
}
function compose(u, v) {
return v.map(e => u[e]);
}
function expected(input, output) {
assert(isEqual(input, output));
return output;
}
id = x => x
errorOptions = ({
errorsEnabled: false,
})
{ // Dangerous things, but can extend default Array chaining methods
Array.prototype.all = function() { return this.reduce((x, y) => x && y, true) };
Array.prototype.any = function() { return this.reduce((x, y) => x || y, false) };
Array.prototype.last = function() {
assert(this.length > 0);
return this[this.length - 1];
};
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
