5

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

假设我们有 3 个项目{A, B, C}。我们想要 2 个项目的排列。这将是3 P 2：

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

但是，如果我们允许最多重复两次。会是什么样子？（我真的不知道。）

我试着想象我们从 set 中得到一个 2 的排列{A, A, B, B, C, C}。这将是6 P 2 = 30。但我们必须删除那些重复项。我是手工完成的，它是 9。我不知道如何从数学中计算 9。

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

（实际上3 P 2重复 2 并不是一个很好的例子。这是因为排列中只有 2 个元素。因此，无限重复之间没有区别。重复 2 的4 P 3将是一个更好的例子。但很难列出所有排列。）

一个更好的例子：4 P 3 of set {A, B, C, D}：

{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 的4 P 3组：{A, B, C, D}

{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, ... }

这是一个谈论类似事情的网页。但它似乎需要n P n（选择所有元素）。此外，我仍然需要一种算法来生成和列出排列。

感谢您的帮助！

对于编程实现，其实有一种“不聪明”的做法。

对于 set {A, B, C, D}，保留一个互补数组int used[0, 0, 0, 0]，即每个元素的使用次数。每次选择一个元素时增加计数，并将数组的副本向前传递（沿着调用树向下）。然后使用此处启发的递归方法，对其进行更改以允许无限重复（通过不从元素集中删除选定的元素），并if (used[i] <= LIMIT)在for.

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

4

4 回答 4

1

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

于 2013-07-13T01:38:53.360 回答
1

好吧，这有点晚了，但我在 GitHub 上有一个Java Combinatorics库可以做到这一点。下面是基本用法：

在项目中包含依赖项：

<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 的快照存储库中找到。

于 2015-01-06T16:13:13.903 回答
0

请参阅这篇论文，该论文找到了答案数量的理论公式。论文信息是：Roberto Frucht 来自 Journal of Combinatorial Theory 的“有限重复的排列”，doi 为 10.1016/S0021-9800(66)80025-X

于 2014-01-24T00:51:12.217 回答
0

您可以将排列视为二进制进位处理。例如，二进制的 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]
于 2022-02-11T09:09:15.060 回答