有限重复排列的算法

Question

有没有一种算法可以列出所有的具有有限重复的排列？如果有现成的Java库，那就太好了！

假设我们有三个项目{A，B，C}。我们希望得到两个项目的排列。这将是₃P₂：

{A, B}
{A, C}
{B, A}
{B, C}
{C, A}
{C, B}

如果我们允许最多重复两次，会是什么情况呢？（我不太清楚。）

我试图想象从集合{A, A, B, B, C, C}中获取2个排列的情况。这将是₆P₂ = 30。但我们必须去掉那些重复的。我手动计算了一下，结果为9。我不知道如何用数学计算出9。

{A, A}
{A, B}
{A, C}
{B, B}
{B, A}
{B, C}
{C, C}
{C, A}
{C, B}

实际上，₃P₂重复2次不是一个好的例子。因为排列中只有2个元素，所以无限重复没有任何区别。₄P₃重复2次将是一个更好的例子。但是列出所有排列可能会很困难。

一个更好的例子是从集合{A，B，C，D}中选择₄P₃：

{A, B, C}
{A, B, D}
{A, C, B}
{A, C, D}
{A, D, B}
{A, D, C}
... repeat for permutations starting from {B, ... }
... repeat for permutations starting from {C, ... }
... repeat for permutations starting from {D, ... }

在具有重复限制为2的集合{A，B，C，D}中，₄P₃ 是多少：

{A, A, B}
{A, A, C}
{A, A, D}

{A, B, A}
{A, B, B}
{A, B, C}
{A, B, D}

{A, C, A}
{A, C, B}
{A, C, C}
{A, C, D}

{A, D, A}
{A, D, B}
{A, D, C}
{A, D, D}

... repeat for permutations starting from {B, ... }
... repeat for permutations starting from {C, ... }
... repeat for permutations starting from {D, ... }

这里有一个相关的网页，但它需要 _nP_n（选择所有元素）。此外，我仍然需要一种生成和列举排列的算法。

谢谢你的帮助！

---

对于程序实现，实际上有一种“不聪明”的方法。

对于集合{A，B，C，D}，保留一个补充数组int used [0,0,0,0]，它是每个元素使用次数的数字。每次选择一个元素时增加计数，并将数组的副本向前传递（沿着调用树）。然后按照这里所示的启发式递归方法进行修改，以允许无限重复（通过不删除从元素集中选择的元素），并在for之后添加if (used [i] <= LIMIT)检查语句。

这是“不聪明”的，也不够好，因为我们需要一个补充数组并要求每次都检查使用数量。

- midnite

---

生成 {A, B, C} 的排列（任意长度）并允许每个元素重复一次，是否与生成相同长度的 {A, A, B, B, C, C} 的排列相同？ - beaker

当长度为3时，如果{A, A, B, B, C, C}的元素是不同的，即A != A，那么它将是P(6, 3)，但会出现重复的{A, A, B}和{A, A, B}，这是不想要的。 - midnite

从技术上讲，一个集合不允许重复。 - mor

@ricard.m.o，嗯...你是说nPr / 排列不能处理重复元素吗？如果是这样，我们可能需要另想一种方法。 - midnite

排列是一种特定的有序序列，其中元素仅出现一次。https://zh.wikipedia.org/wiki/%E6%8E%92%E5%88%97 - mor

Answer 1

好的，虽然有点晚了，但我在GitHub上有一个Java组合库，可以完成此操作。以下是基本用法：

将依赖项包含到您的项目中：

<dependency>
  <groupId>com.xiantrimble.combinatorics</groupId>
  <artifactId>combinatorics</artifactId>
  <version>0.2.0</version>
<dependency>

然后，通过从组合工厂中获取虚拟集合来迭代排列：

import com.xiantrimble.combinatorics.CombinatoricFactory;
import com.xiantrimble.combinatorics.CombinatoricFactoryImpl;
import com.xiantrimble.combinatorics.Combinatoric;
...
int k = 6;
int[] domain = {1,1,1,1,2,2,2,3,3,4};
// create a factory.
CombinatoricFactory factory = new CombinatoricFactoryImpl();
Combinatoric<Integer> permutations = factory.createPermutations(k,  domain);

for( Integer[] permutation : permutations ) {
  System.out.println(Arrays.toString(permutation));
}

代码不是按照字典顺序排序的，而是旨在尽量减少相邻元素之间的变化，请注意。此外，在0.3.0-SNAPSHOT版本中有一些改进，可在Sonatype的快照存储库中获取。

- Christian Trimble

Answer 2

我以前遇到过一个问题，需要生成集合的所有可能分区。这本质上与您尝试做的事情相同。（给定大小的所有组合与该大小的分区集相同）我发现this 这篇论文提供了一种非递归算法来快速生成这些组合，而且不会有任何重复，并提供了c++实现。

- user545199

---

请勿仅发布链接答案，如果链接失效，则此答案毫无价值。请尝试将主要思想融入您的答案中。 - Kuba Spatny

Answer 3

您可以将排列视为二进制进位处理。例如，0000、0001、0010等二进制数。

 public static int[][] permutation(int size,int carryNum) {
    if(size == 0)
        return new int[0][0];

    int s = size - 1;
    int cNum = carryNum - 1;
    int s1 = 1;
    for(int i=0;i<size;i++){
        s1 = s1 * carryNum ;
    }
    int[][] commands = new int[s1][size];
    for (int i = 1; i < s1; i++) {

        for (int j = s; j >= 0; j--) {
            commands[i][j] = commands[i - 1][j];
        }

        for (int j = s; j >= 0; j--) {
            int last = commands[i][j];
            if ((last + 1) > cNum) {
                commands[i][j] = 0;
            } else {
                commands[i][j] = last + 1;
                break;
            }
        }
    }
    return commands;
}

public static void main(String[] args) {

    int[][] s = permutation(7,3);
    for (int[] command : s) {
        System.out.println(Arrays.toString(command));
    }
}

output result:

[0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 1]

[0, 0, 0, 0, 0, 0, 2]
          .
          .
          .
[0, 0, 0, 0, 2, 0, 2]

[2, 2, 2, 2, 2, 2, 2]

- Joe

Answer 4

请查看这篇论文，它找到了一个关于答案数量的理论公式。 该论文信息为："Permutations with limited repetitions"，作者为Roberto Frucht，发表在《组合数学杂志》上，doi为10.1016/S0021-9800(66)80025-X。

- Masood_mj

---

请勿仅发布链接答案，如果链接失效，则此答案毫无价值。请尝试将主要思想融入您的答案中。 - Kuba Spatny