找到第n个排列而不计算其他排列

Question

给定表示置换原子的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大小的排列,这不是我的情况.

谢谢.

Answer 1

正如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

Answer 2

这是一个允许选择排列大小的解决方案.例如,除了能够生成10个元素的所有排列之外,它还可以生成10个元素中的对的排列.它还会置换任意对象的列表,而不仅仅是整数.

这是PHP,但也有JavaScript和Haskell实现.

function nth_permutation($atoms, $index, $size) {
    for ($i = 0; $i < $size; $i++) {
        $item = $index % count($atoms);
        $index = floor($index / count($atoms));
        $result[] = $atoms[$item];
        array_splice($atoms, $item, 1);
    }
    return $result;
}

用法示例:

for ($i = 0; $i < 6; $i++) {
    print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
// => AB, BA, CA, AC, BC, CB

它是如何工作的？

它背后有一个非常有趣的想法.我们来看看清单A, B, C, D.我们可以通过从卡片中抽取元素来构造排列.最初我们可以绘制四个元素中的一个.然后剩下的三个元素中的一个,依此类推,直到最后我们什么都没有留下.

这是一种可能的选择顺序.从顶部开始,我们采取第三条路径,然后是第一条路径,第二条路径,最后是第一条路径.这就是我们的排列#13.

考虑一下如果选择这一系列,您将在算法上得到十三个数字.然后反转你的算法,这就是你如何从一个整数重建序列.

让我们试着找到一个通用方案,将一系列选择打包成一个没有冗余的整数,然后将其解包.

一个有趣的方案叫做十进制数字系统."27"可以被认为是从10中选择路径#2,然后从10中选择路径#7.

但每个数字只能编码来自10个替代品的选择.具有固定基数的其他系统,如二进制和十六进制,也只能编码来自固定数量的备选方案的选择序列.我们想要一个具有可变基数的系统,类似于时间单位,"14:05:29"是小时14从24,分钟5从60,第二个29从60.

如果我们采用通用的数字到字符串和字符串到数字的功能,并欺骗它们使用混合基数怎么办？而不是采用单个基数,如parseInt('beef',16)和(48879).toString(16),它们将每个数字取一个基数.

function pack(digits, radixes) {
    var n = 0;
    for (var i = 0; i < digits.length; i++) {
        n = n * radixes[i] + digits[i];
    }
    return n;
}

function unpack(n, radixes) {
    var digits = [];
    for (var i = radixes.length - 1; i >= 0; i--) {
        digits.unshift(n % radixes[i]);
        n = Math.floor(n / radixes[i]);
    }
    return digits;
}

这甚至有用吗？

// Decimal system
pack([4, 2], [10, 10]); // => 42

// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); // => 42

// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); // => 42

现在倒退了:

unpack(42, [10, 10]); // => [4, 2]

unpack(42, [5, 4, 3, 2, 1]); // => [1, 3, 0, 0, 0]

这真是太美了.现在让我们将这个参数数字系统应用于排列问题.我们将考虑长度为2的排列A, B, C, D.它们的总数是多少？让我们看看:首先我们绘制4个项目中的一个,然后是其余3个中的一个,这是4 * 3 = 12绘制2个项目的方法.这12种方式可以打包成整数[0..11].所以,让我们假装我们已经打包它们,并尝试解压缩:

for (var i = 0; i < 12; i++) {
    console.log(unpack(i, [4, 3]));
}

// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]

这些数字表示选择,而不是原始数组中的索引.[0,0]并不意味着服用A, A,它意味着从A, B, C, D(那是A)中获取项目#0 ,然后从剩余列表中获取项目#0 B, C, D(即B).由此产生的排列是A, B.

另一个例子:[3,2]意味着从A, B, C, D(那是D)中获取项目#3 ,然后从剩余列表中获取项目#2 A, B, C(即C).由此产生的排列是D, C.

此映射称为Lehmer代码.让我们将所有这些Lehmer代码映射到排列:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

这正是我们所需要的.但是如果你看一下这个unpack函数,你会注意到它从右到左产生数字(反转动作pack).3中的选择在从4中选择之前被解压缩.这是不幸的,因为我们想在从3中选择之前从4个元素中进行选择.如果不能这样做,我们必须首先计算Lehmer代码,将其累积到临时数组中,然后将其应用于项目数组以计算实际排列.

但是如果我们不关心字典顺序,我们可以假装我们想在从4中选择之前从3个元素中进行选择.然后从4中选择将从unpack第一个开始.换句话说,我们将使用unpack(n, [3, 4])而不是unpack(n, [4, 3]).这个技巧允许计算Lehmer代码的下一个数字并立即将其应用于列表.而这正是如何nth_permutation()运作的.

我要提到的最后一件事unpack(i, [4, 3])是与阶乘数系统密切相关.再看一下第一棵树,如果我们想要长度为2而没有重复的排列,我们可以跳过每一秒的排列索引.这将给我们12个长度为4的排列,可以修剪为长度2.

for (var i = 0; i < 12; i++) {
    var lehmer = unpack(i * 2, [4, 3, 2, 1]); // Factorial number system
    console.log(lehmer.slice(0, 2));
}

Answer 3

这取决于你"排序"你的排列的方式(例如词典顺序).

一种方法是使用阶乘数系统,它为你提供[0,n!]和所有排列之间的双射.

然后,对于[0,n!]中的任何数字i,您可以计算第i个排列,而无需计算其他数字.

这种因子写作基于以下事实:[0和n!]之间的任何数字都可以写成:

SUM( ai.(i!) for i in range [0,n-1]) where ai <i 

(它与基本分解非常相似)

有关此分解的更多信息,请查看此主题:https://math.stackexchange.com/questions/53262/factorial-decomposition-of-integers

希望能帮助到你

正如这篇维基百科文章所述,这种方法相当于计算lehmer代码:

生成n的排列的一种显而易见的方法是生成Lehmer代码的值(可能使用最多为n!的整数的阶乘数系统表示),并将它们转换为相应的排列.然而,后一步骤虽然简单,但难以有效地实现,因为它需要从序列中选择和从中删除每个操作,在任意位置; 作为数组或链表的序列的明显表示,都需要(出于不同的原因)关于n2/4操作来执行转换.由于n可能相当小(特别是如果需要生成所有排列),这不是一个问题,但事实证明,无论是随机还是系统生成,都有简单的替代方案可以做得更好.由于这个原因,使用一种特殊的数据结构似乎没有用,虽然这是可行的,这种结构允许在O(n log n)时间内执行从Lehmer代码到置换的转换.

因此,对于一组n元素,您可以做的最好的是具有适应数据结构的O(n ln(n)).

Answer 4

这是一种在线性时间内在排列和排名之间进行转换的算法.但是,它使用的排名不是词典.这很奇怪,但一致.我将给出两个函数,一个从一个等级转换为一个置换,另一个用于反转.

首先,要排名(从排名到排列)

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

接下来,排名:

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q[s], q[n-1])
  return s + n * rank(n-1, p, q)
end

这两者的运行时间都是O(n).

有一篇很好的,可读的论文解释了它的工作原理:线性时间的排名和排名排列,Myrvold和Ruskey,信息处理快报,第79卷,第6期,2001年9月30日,第281-284页.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Answer 5

这是python中的一个简短且非常快(元素数量的线性)解决方案,适用于任何元素列表(下面示例中的13个第一个字母):

from math import factorial

def nthPerm(n,elems):#with n from 0
    if(len(elems) == 1):
        return elems[0]
    sizeGroup = factorial(len(elems)-1)
    q,r = divmod(n,sizeGroup)
    v = elems[q]
    elems.remove(v)
    return v + ", " + ithPerm(r,elems)

例子 :

letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m']

ithPerm(0,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, k, l, m
ithPerm(4,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, m, k, l
ithPerm(3587542868,letters[:]) #--> h, f, l, i, c, k, a, e, g, m, d, b, j

注意:我给letters[:](副本letters)而不是字母,因为函数修改了它的参数elems(删除了所选元素)