大きな要素集合のn番目の置換を取得

Question

可能なすべての置換で36個の数字のセットを並べるJavaScriptプログラムを作成したいと思います。 （毎秒10の順列）。これらの数字を整理するには36の要因があります。 はい、私は私のプログラムが地球の終わりまで終わらないことを知っています:)（それは私が示したいものです）。

それは次の順序で始まる：

1. 順列：0,1,2,3,4,5,6、...、32,33,34,35
2. 順列：0 1,2,3,4,5,6、...、32,33,35,34
3. 順列：0,1,2,3,4,5,6、...、32,34 、33,35

.....（ここでは多くの順列）....

は、cの方法はあります直前のものをすべて計算することなく5分15秒の1000分の1（1000分の1秒後の時間）の順列を計算しますか？ 文字通り、永遠にかかる前のものを計算してください！

また、私が5分15秒の1000番目の順列を知っているなら、次の計算をする方法が必要です。 私が見つけたすべての置換アルゴリズムはすべての順列を一度に計算します。その多くの順列では選択肢ではありません。

これも可能なのですか、それともやる気でしょうか？

ご入力のためのThxを

Answer 1

二つの関数である：

• getPermutationByRank：そのランク数により置換（配列）を取得します。インスピレーションはthis answerから取られました。
• nextPermutation：指定された順列を次の順番に変更します。インスピレーションはthis answer基本的には何が必要です

から取られたが、私は以降、特定のランクから順列を生成するために、上記の二つの機能を使用して発電機を、追加しています。

最後に、書式化関数は、指定された置換を文字セットに変換します（10桁+ 26文字= 36個の異なる文字）。

スニペットは2000-01-01ためデシ秒の現在の数を計算し、対応する順列を出力し、次の順列に移る毎デシ秒それを更新：

// 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 }

免責事項：

1. この（5293000000のように）あなたが尋ねるランク番号で動作しますが、ランクがJavaScriptが提供できる精度を超えると、結果は間違っています。実際、第1の関数で計算される階乗は、精度が失われた後、18!までしか正確ではありません。ランクがJavaScriptがサポートする範囲（約16桁）内であれば、アルゴリズムには何の影響もありません。したがって、第1の機能にはセーフガードがあります。

2. setIntervalは、時間の経過に合わせるための信頼性の高い方法ではありません。しばらくすると、最初の繰り返しから経過した実数のデシ秒と同期が外れる可能性があります。しかし、これはあなたの目的のために重要ではないようでした。そうであれば、の漂流を補うためにthis answerを見てください。

Answer 2

これは、次の状態を取得するために与えられた順列の状態のための提案です。

これは2つのルールによって行われます。

1. 最も右の項目がこれら2つのアイテムを交換

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

   のように、前の項目よりも大きい場合。

2. 左側と右側で1つ以上のアイテムの右側から検索します。ここ

   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>