Obtenir la n-ième permutation d'un grand ensemble d'éléments

Question

Je voudrais écrire un programme JavaScript qui organise un ensemble de 36 nombres dans toutes les permutations possibles. (10 permutations par seconde). Il y a 36 manières factorielles d'organiser ces nombres. Oui je sais que mon programme ne se terminera pas jusqu'à la fin de la terre :) (c'est exactement ce que je veux montrer).

Il commence par la séquence suivante:

1. permutation: 0,1,2,3,4,5,6, ..., 32,33,34,35
2. permutation: 0 , 1,2,3,4,5,6, ..., 32,33,35,34
3. permutation: 0,1,2,3,4,5,6, ..., 32,34 , 33,35

..... (beaucoup plus permutations ici) ....

est-il un moyen de c alculer les 5'595'000'000e (temps en decisecondes depuis le 01.01.2000) permutation sans calculer tous les précédents? Calculer les précédents prendrait littéralement pour toujours!

De plus, si je connais la 5'595'000'000e permutation, j'ai besoin d'un moyen de calculer le suivant. Tous les algorithmes de permutation que j'ai trouvés calculent toutes les permutations à la fois. Ce qui n'est pas une option avec autant de permutations. Est-ce encore possible ou suis-je condamné?

Thx pour votre entrée

Answer 1

Voici deux fonctions:

• getPermutationByRank: obtient une permutation (tableau) par son numéro de rang. Inspiration tirée de this answer;
• nextPermutation: mute une permutation donnée à la suivante dans l'ordre. Inspiration tirée de this answer

C'est essentiellement ce que vous avez besoin, mais je l'ai ajouté un générateur, qui utilise les deux fonctions pour générer des permutations à partir d'un certain rang partir ci-dessus.

Enfin une fonction de formatage traduit une permutation donnée en un jeu de caractères (10 chiffres + 26 lettres = 36 caractères différents).

L'extrait calcule le nombre actuel de déci secondes depuis 2000-01-01 et sorties la permutation correspondante, la mise à jour à la prochaine permutation tous les déci-seconde qui passe:

// See https://stackoverflow.com/a/7919887/5459839 
 
function getPermutationByRank(n, rank) { 
 
    // Sageguard for inaccurate calculations: rank <= 9007199254740991 
 
    if (rank > Number.MAX_SAFE_INTEGER) throw "Too large rank for JavaScript"; 
 
    var perm = (function loop(i, fact) { 
 
     // Calculate factorials and subtract from rank from highest to lowest 
 
     return i > n ? [] : 
 
       [loop(i+1, fact * i).concat(Math.floor(rank/fact) % n), 
 
       rank = rank % fact][0]; 
 
    })(1, 1); 
 
    // Readjust values to obtain the permutation 
 
    // start from the end and check if preceding values are lower 
 
    for (let k = n - 1; k > 0; --k) 
 
     for (let j = k - 1; j >= 0; --j) 
 
     if (perm[j] <= perm[k]) 
 
      perm[k]++; 
 
    return perm; 
 
} 
 

 
// See https://stackoverflow.com/a/1622539/5459839: 
 
function nextPermutation(perm) { 
 
    // Find longest non-increasing suffix 
 
    var i = perm.length - 2; 
 
    while (i >= 0 && perm[i] >= perm[i + 1]) 
 
     i--; 
 
    // Now i is the head index of the suffix 
 
    
 
    // Are we at the last permutation already? 
 
    if (i < 0) return; // no more permuations 
 
    
 
    // Let perm[i] be the pivot 
 
    // Find rightmost element that exceeds the pivot 
 
    var j = perm.length - 1; 
 
    while (perm[j] <= perm[i]) 
 
     j--; 
 
    // Now the value perm[j] will become the new pivot 
 
    // Assertion: j >= i 
 
    
 
    // Swap the pivot with j 
 
    [perm[i], perm[j]] = [perm[j], perm[i]]; 
 
    
 
    // Reverse the suffix 
 
    j = perm.length - 1; 
 
    i++; 
 
    while (i < j) { 
 
     [perm[i], perm[j]] = [perm[j], perm[i]]; 
 
     i++; 
 
     j--; 
 
    } 
 
    return perm; 
 
} 
 

 
// Create a generator using above two functions: 
 
function* generatePermutationsFrom(n, rank) { 
 
    var perm = getPermutationByRank(n, rank); 
 

 
    yield perm; 
 
    while (nextPermutation(perm)) { 
 
     yield perm; 
 
    } 
 
} 
 

 
// Utility functions for OP specific requirements 
 
function deciSecondsSince(dt) { 
 
    return Math.floor((Date.now() - dt.getTime())/100); 
 
} 
 

 
function permToString(perm) { 
 
    var chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; 
 
    return perm.map (v => chars[v]).join(''); 
 
} 
 

 
var deciSecs = deciSecondsSince(new Date('2000-01-01')); // ~5293000000 
 
var iter = generatePermutationsFrom(36, deciSecs); 
 

 
// Output next permuation every decisecond: 
 
document.body.textContent = permToString(iter.next().value); 
 
setInterval(function() { 
 
    document.body.textContent = permToString(iter.next().value); 
 
}, 100);

body { font-family: monospace }

: Avertissements

1. cette fonctionne pour les numéros de rang que vous demandez (comme 5293000000), mais si le rang dépasse la précision que JavaScript peut offrir, les résultats seront faux. En effet, les factorielles qui sont calculées dans la première fonction ne sont précises qu'à 18!, après quoi elles perdent de la précision. Cela n'a aucun impact sur l'algorithme tant que votre rang se situe dans la plage prise en charge par JavaScript (environ 16 chiffres). La première fonction a donc une sauvegarde.

2. setInterval est pas une façon très fiable pour suivre le rythme avec le temps, après un certain temps les itérations numéro peut se désynchroniser avec le nombre réel de déci secondes qui est passé depuis la première itération. Mais cela ne semblait pas si important pour vos objectifs. Si c'est le cas, jetez un oeil à this answer pour compenser à la dérive.

Answer 2

Ceci est une proposition de l'état de permutation donnée pour obtenir l'état suivant.

Ceci est fait par deux règles.

1. Si le plus droit article est supérieur à l'élément avant, comme

   1 < 2 < 3 < 4 < 5 
         ^^^
   1 2 3 5 4 
   

   puis changez ces deux éléments.

2. Rechercher de droite pour un élément qui est supérieur à un élément sur le côté gauche et le côté droit.

   2 <5> 3 <4> 1 
        ^^^^^
   _____| |_________ take the right group, get the next higher value (4) of the most left 
   left  right (3) in this group, add it to the left group and sort the right group 
           and append it to the left group. 
   2 5 4 1 3 
   

function swap(array) { 
 
    var l = array.length, 
 
     i = l - 2, 
 
     temp, 
 
     right; 
 

 
    if (array[l - 2] < array[l - 1]) { 
 
     temp = array[l - 1]; 
 
     array[l - 1] = array[l - 2]; 
 
     array[l - 2] = temp; 
 
     return; 
 
    } 
 
    while (i > 0) { 
 
     if (array[i - 1] < array[i] && array[i] > array[i + 1]) { 
 
      right = array.splice(i - 1, l - i + 1); 
 
      temp = right[0]; 
 
      right.sort(function (a, b) { return a - b; }); 
 
      array.push(right.splice(right.indexOf(temp) + 1, 1)[0]); 
 
      array.splice.apply(array, [3, 0].concat(right)); 
 
      return; 
 
     } 
 
     i--; 
 
    } 
 
} 
 

 
var i = 0, 
 
    data = [1, 2, 3, 4, 5]; 
 

 
while (i++ < 120) { 
 
    swap(data); 
 
    document.getElementById('out').innerHTML += data.join(' ') + '\n'; 
 
}

<pre id="out"></pre>