获取int 的排列删除重复集
我有一个[]的整数1 <= N 数组可能包含重复项，因此得到的排列集可能是重复的，因此需要获得所有非重复的排列。
- 我发现很多片段会将int []转换为字符串并执行排列和打印输出，但是因为我这里是范围1 <= N <= 100的整数，所以将它们转换为字符串会破坏整数。
- 我可以获得所有重复项的排列，包括最后一组排列，删除重复项必须检查
彼此删除一个副本左右，它是如此繁重的过程。
有没有更简单的方法？
例如：123会给
231 321 312 132 213 123 同样地，112计划会给
121 211 211 121 112 112
因此，对于n组元素，排列将是n！ 随着元素中的重复，将减少，我问我如何删除这些重复集。 （重复的置换集合arr []）
如果首先对词素进行词法排序是可以接受的，那么你就可以进行词汇排列。 包括为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]开始，您不再获得更多排列（与上面的示例相比）。
您可以使用Set而不是int数组，它可以自动删除您的重复。
编辑： @allingeek给我一个主意。 除了实现你自己的Set之外，你可以在int上编写一个包装器并覆盖你的equals和hashcode方法，找到你的排列等于的方式。 也许按顺序使用数字和其他人在“Effective Java”中给出建议（对于equals和hashcode实现以避免错误）。 它可以为您提供更好的方法来查找Set中的排列。 不像我刚开始说的那样使用表达式语言。
您需要数组的所有非重复排列。 这些数量，假设每个数组条目是唯一的，Factorial（array.length），很快变得不可复制。 但假设您想要枚举它们，最简单的方法是执行以下操作：
您的问题基本上是您的字母表中的选择问题（1 <= N <= 100）。 如果您想要选择其中的5个或500个无关紧要，您想要选择一些数字，将其称为x。 想想你想要选择的独特元素，那些你不想复制的元素（这可能是你的字母表的合适子集，或者不是）。 将这些元素连续放置。 这一行的长度是n。 现在，列举这些x的选择的选择问题可以如下解决。 想想一个n位数，它只能包含nx个零。 要获得此rank-x数，只需从0开始并枚举所有可能的数字，最多为2 ** n，仅选择具有x 1s（和nx零）的数字。 这些1然后从您的字母表的n个位置选择x个位置，并且这些rank-x数字中的每一个都为您选择一个排列。
如果有人知道优化，以便您不必计算所有非rank-x，请说出来。 编辑：似乎答案就在这里
删除重复元素的最简单方法是将内容添加到不允许重复的Set中，然后将Set添加回ArrayList ，如下所示。
ArrayListal=new ArrayList (); al.add(String.valueOf(arr[0])); //Just as an example. HashSet hs = new HashSet(); hs.addAll(al); al.clear(); al.addAll(hs);
- 对数组进行排序。
- 使用嵌套循环，其中外部循环遍历数组中的每个元素。 如果下一个元素与最后一个元素具有相同的值，则跳过。 然后内部循环将该元素放置在列表中的每个位置。 在每个循环上保存排列。
这将生成排列以及跳过重复排列。
int[] sortedSourceArray = ...; int last = -1; int current = -1; // build one permutation with the original array buildPermutation(permutationList, sortedSourceArray); // I'm not going to implement this for you. for (int i = 0; i < sortedSourceArray.length; i++) { current = sortedSourceArray[i]; // check if the new value is the same as the last if(current == last) continue; // remove the current element from the list // build your permutations for(int j = 0; j < sortedSourceArray.length; j++) { // skip if its inserting the element at its original position if(j == i) continue; // fix the duplicates for blocks of repeated elements if(j < sortedSourceArray.length-1 && sortedSourceArray[j+1] == current) continue; // inject the current element at the new position inject(sortedSourceArray, current, j); // build the permutation buildPermutation(permutationList, sortedSourceArray); // remove the current element from that position remove(sortedSourceArray, j); } last = current; }
编辑：实际上我认为这需要进一步调整以捕获最后几个生成重复项的情况。 这将是重复元素插入其相同值旁边的位置。 我已经适当地更改了代码。