Skip to content Skip to sidebar Skip to footer

Js: How To Create An Array Containing Permutations Of A Sequence 0 To N In Which Adjacent Numbers Must Have A Difference Greater Than 1?

Just to elaborate on the question asked. Given that you have a sequence from 0 to n (0,1,2, ... n-1,n). I want to return an array that contains all the possible permutations that f

Solution 1:

You'll definitely need something more elegant to make the code maintainable. I'd recommend to start with a normal recursive solution, maybe a fancy (and efficient) generator function:

function* permutations(array, i) {
    if (i >= array.length)
        yield array;
    else
        for (let j=i; j<array.length; j++)
            yield* permutations([
                ...array.slice(0, i),
                array[j],
                ...array.slice(i, j),
                ...array.slice(j+1)
            ], i+1);
}
Array.from(permutations(['a', 'b', 'c', 'd'], 0))

Now all you need to do is add the condition for neighbouring elements:

function* permutations(array, i) {
    if (i >= array.length)
        yield array;
    else
        for (let j=i; j<array.length; j++)
            if (i == 0 || Math.abs(array[i-1] - array[j]) > 1)
                yield* permutations([
                    ...array.slice(0, i),
                    array[j],
                    ...array.slice(i, j),
                    ...array.slice(j+1)
                ], i+1);
}
Array.from(permutations([0, 1, 2, 3], 0))

Anything above sequences up to 0-7 will take a ridiculous amount of time

That's rather normal. There are many, many permutations for array of that size, and your condition only filters out a few of them. Here's a quick table:

length | number of solutions
-------+---------------------
 0     | 1
 1     | 1
 2     | 0
 3     | 0
 4     | 2
 5     | 14
 6     | 90
 7     | 646
 8     | 5242
 9     | 47622
 10    | 479306

…aka OEIS A002464 :-)


Post a Comment for "Js: How To Create An Array Containing Permutations Of A Sequence 0 To N In Which Adjacent Numbers Must Have A Difference Greater Than 1?"