获取删除重复集的int[]的排列

Question

我有一个整数数组1<=N<=100，如何获得这个数组的排列？数组可能包含重复项，因此所产生的一组排列可能是重复的，因此需要获取所有非重复排列。

• 我已经找到了很多代码片段，它们可以将int[]转换为字符串，并执行排列和打印输出，但是由于这里的hv是范围1<=N<=100的整数，所以将它们转换为字符串会破坏整数。
• 我可以得到所有的排列与重复，包括，对于最后一组排列，其中的重复被删除，必须检查彼此删除一个重复左右，这是如此繁重的过程。

有没有更简单的方法？

例如，123将提供：

231
321
312
132
213
123

类似地，对于112程序，可以提供：

121
211
211
121
112
112

因此，对于元素的n-set，排列将是具有重复元素的n!，这将减少。我在问我怎么才能删除那些重复的集合。(重复排列的arr[])

Answer 1

如果首先对元素进行词汇排序是可以接受的，那么您就可以进行词汇排列。包括一种算法，用于一个int数组，很容易修改字符串。

public static boolean permuteLexically(int[] data) {
    int k = data.length - 2;
    while (data[k] >= data[k + 1]) {
        k--;
        if (k < 0) {
            return false;
        }
    }
    int l = data.length - 1;
    while (data[k] >= data[l]) {
        l--;
    }
    swap(data, k, l);
    int length = data.length - (k + 1);
    for (int i = 0; i < length / 2; i++) {
        swap(data, k + 1 + i, data.length - i - 1);
    }
    return true;
}

如何使用它的示例

public static void main(String[] args) {
    int[] data = { 1,2,3 };
    do {
        System.err.println(Arrays.toString(data));
    } while(Util.permuteLexically(data));
}

把这个和1,2,3一起使用

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

用1,1,3你可以得到

[1, 1, 3]
[1, 3, 1]
[3, 1, 1]

我想这就是你想要的。

由于该方法按字典顺序重新调整“下一步”排列，因此对元素进行排序是很重要的。从3，2，1开始，就不会有更多的排列(与上面的例子相比)。

Answer 2

您可以使用一个http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Set.html代替一个it数组，它可以自动删除您的复制。

编辑： @allingeek给我一个想法。除了实现您自己的http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Set.html之外，您还可以在int上编写一个包装器，并覆盖您的equals方法，找到您的排列相等的方式。也许是按照顺序使用数字，其他人建议使用“有效Java”(用于等于和哈希代码实现，以避免错误)。它可以给你一个更好的方法来找到你在http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Set.html中的排列。不只是像我刚开始说的那样使用表达语言。

Answer 3

你想要一个数组的所有非重复排列。假设每个数组条目都是唯一的，这些元素的数量很快就会变得不可计算的大。但是，假设您希望枚举它们，最简单的方法是执行以下操作：

你的问题基本上是你的字母表上的选择问题(1 <= N <= 100)。如果您想选择其中的5个或500个并不重要，您需要选择某个数字，调用它，x。想想您想要从中选择的唯一元素，那些您不想重复的元素(这可能是您的字母表的适当子集，或者不是)。把这些元素排成一行。这一行的长度是n。现在，枚举其中x的选择的选择问题可以解决如下。假设一个n位数，它只能包含n零。要获得这个秩-x数，只需从0开始，并枚举所有可能的数字，最多2**n，只选择那些具有x1s(和n零)的数字。然后，这些1s从字母的n个位置中选择x个位置，而这些秩x数字中的每一个都为您选择一个排列。

如果有人知道一个优化，所以你不需要计算出所有的非秩x，请这样说。编辑:答案似乎是这里