已解決430363個問題，去搜搜看，總會有你想問的

找到第n個排列而不計算其他排列

首頁猿問找到第n個排列而不計算其他排列

找到第n個排列而不計算其他排列

PHP 算法算法與數據結構

慕碼人2483693 2019-08-12 18:43:50

找到第n個排列而不計算其他排列給定表示置換原子的N個元素的數組，是否有類似的算法：function getNthPermutation( $atoms, $permutation_index, $size )其中$atoms是元素數組，$permutation_index是置換的索引，是置換$size的大小。例如：$atoms = array( 'A', 'B', 'C' );// getting third permutation of 2 elements$perm = getNthPermutation( $atoms, 3, 2 );echo implode( ', ', $perm )."\n";會打印：B, A沒有計算每個排列直到$ permutation_index？我聽說過關于事實排列的一些事情，但我發現的每一個實現都會給出一個具有相同V大小的排列，這不是我的情況。

查看完整描述

3 回答

翻翻過去那場雪

TA貢獻2065條經驗獲得超14個贊

正如RickyBobby所說，在考慮排列的詞典順序時，你應該利用因子分解。

從實際的角度來看，這就是我的看法：

執行排序歐幾里德師，除非你用階乘數字做，首先(n-1)!，(n-2)!等。
將商保留在數組中。該i個商應該是一個數之間0和n-i-1包容性的，其中i從去0到n-1。
這個數組就是你的排列。問題是每個商不關心以前的值，所以你需要調整它們。更明確地說，您需要將每個值遞增多次，因為之前的值較低或相等。

以下C代碼應該讓您了解它是如何工作的（n是條目數，并且i是排列的索引）：

/**
 * @param n The number of entries
 * @param i The index of the permutation
 */void ithPermutation(const int n, int i){
   int j, k = 0;
   int *fact = (int *)calloc(n, sizeof(int));
   int *perm = (int *)calloc(n, sizeof(int));

   // compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

   // compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = i / fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

   // readjust values to obtain the permutation
   // start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

   // print permutation
   for (k = 0; k < n; ++k)
      printf("%d ", perm[k]);
   printf("\n");

   free(fact);
   free(perm);}

例如，ithPermutation(10, 3628799)按預期打印十個元素的最后一個排列：

9 8 7 6 5 4 3 2 1 0

反對回復 2019-08-12

3 回答
0 關注
735 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

找到第n個排列而不計算其他排列

找到第n個排列而不計算其他排列

3 回答

添加回答