首頁猿問找到第n個(gè)排列而不計(jì)算其他排列

找到第n個(gè)排列而不計(jì)算其他排列

PHP 算法算法與數(shù)據(jù)結(jié)構(gòu)

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

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

查看完整描述

3 回答

翻翻過去那場雪

TA貢獻(xiàn)2065條經(jīng)驗(yàn) 獲得超14個(gè)贊

正如RickyBobby所說，在考慮排列的詞典順序時(shí)，你應(yīng)該利用因子分解。

從實(shí)際的角度來看，這就是我的看法：

執(zhí)行排序歐幾里德師，除非你用階乘數(shù)字做，首先(n-1)!，(n-2)!等。
將商保留在數(shù)組中。該i個(gè)商應(yīng)該是一個(gè)數(shù)之間0和n-i-1包容性的，其中i從去0到n-1。
這個(gè)數(shù)組就是你的排列。問題是每個(gè)商不關(guān)心以前的值，所以你需要調(diào)整它們。更明確地說，您需要將每個(gè)值遞增多次，因?yàn)橹暗闹递^低或相等。

以下C代碼應(yīng)該讓您了解它是如何工作的（n是條目數(shù)，并且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)按預(yù)期打印十個(gè)元素的最后一個(gè)排列：