0

I am looking to generate one specific arrangement of an array of items, given the items, and some identifier for which arrangement to generate. This should be deterministic (not random).

For example, for three items, there are 6 arrangements. Each time the user visits our site, we want them to see one specific arrangement, chosen based on what they saw last time. ("I saw order #1 ['a', 'b', 'c'] last time, so this time, show me order #2, which is ['a', 'c', 'b']")

const items = ['a', 'b', 'c'];

const possibleArrangements = [
  ['a', 'b', 'c'],
  ['a', 'c', 'b'],
  ['b', 'a', 'c'],
  ['b', 'c', 'a'],
  ['c', 'a', 'b'],
  ['c', 'b', 'a'],
];

There are many ways to generate the entire list of possibilities by brute force, but generating every possible permutation seems overkill for this use case, when all we really need is to get one desired arrangement based on an identifier. Given the same items and the same identifier, I'm looking for a way to generate the same permutation every time, and only that arrangement.

magicFunction(['a', 'b', 'c'], 2)

>> ['b', 'a', 'c']

Suggestions would be welcome; thanks!

abought
  • 2,652
  • 1
  • 18
  • 13
  • Can't you just cache the permutations when the collection is updated? `magicFunction()` would then just pull the requested index. I don't see how you would get `magicFunction(['a', 'b', 'c'], 5)` without generating all permutations on-the-fly to get the last one. – Dan Wilson Nov 23 '16 at 03:57
  • We could hard-code the list of all permutations, but for a 6-item list, that's 720 hard coded items. (it gets big fast) There's no caching because the list of possible arrangements is generated on the front end, and at most the DB will store which arrangement one particular user saw last time. – abought Nov 23 '16 at 04:05
  • 1
    There's this: http://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others It still involves iterating over *something* to get a desired permutation. Maybe it will work for you. – Dan Wilson Nov 23 '16 at 11:55

1 Answers1

1

Use recursion function.
If you want all the possible arrangements, I answered a similar questions here and here

function magicFunction(arr,index){
    // Finds the number of arrangement possibility starts with a character
    // For example there are 2 arrangement possibility that starts with 'a'
    var partsNum = factorial(arr.length - 1);

    // If the index is invalid return undefined
    if (partsNum * arr.length < index + 1 || index < 0){ return; } //Invalid index

    // Find the starting character index of the arrangement 
    var startIndex = 0;
    while (index + 1 > partsNum){
        startIndex++;
        index -= partsNum;
    }

    // Keeps a reference of the starting character
    var startWith = arr[startIndex];

    arr.splice(startIndex,1); //Removes the character from array
    return startWith  + (arr.length > 0 ? magicFunction(arr,index) : "");
}

function factorial(num){
    var ans = 1;
    while (num > 1){
       ans *= num;
       num--;
    }
    return ans;
}

console.log(magicFunction(['a', 'b', 'c'], 0));
console.log(magicFunction(['a', 'b', 'c'], 1));
console.log(magicFunction(['a', 'b', 'c'], 2));
console.log(magicFunction(['a', 'b', 'c'], 3));
console.log(magicFunction(['a', 'b', 'c'], 4));
console.log(magicFunction(['a', 'b', 'c'], 5));
Community
  • 1
  • 1
Thum Choon Tat
  • 3,084
  • 1
  • 22
  • 24
  • If I'm reading this correctly, one drawback is the need to brute-force calculate at least every arrangement up to and including the one desired. This might be be feasible, but as people progress deeper through the site, they'd be doing more and more calculations for each new page visited. Ideally, I'd hope to find a method that could sidestep the unnecessary intermediate work and go directly to a desired state. – abought Nov 23 '16 at 05:17