获取int []的排列删除重复集 [英] Getting permutations of an int[] removing duplicates sets

问题描述

我有一个[]的整数1< = N< = 100，我怎么能得到这个数组的排列？
- >数组可能包含重复项，因此产生的排列组可能重复，因此需要获得所有非重复排列。

I have an [] of integers 1<=N<=100 , How can i get permutations of this array? -> Array may contain duplicates, so resulting set of permutations can be duplicate, so need to get all non-duplicate permutations.

• 我发现很多片段会将int []转换为字符串
  并执行排列和打印输出，但是因为我这里是整数
  范围1< = N< = 100，所以将它们转换为字符串会破坏
  整数。


• 我可以获得包含重复项的所有排列，包括，对于最终的
  排列集，其中重复项被删除必须检查
  
  彼此删除重复项或者说，这个过程非常繁重。

有没有更简单的方法？

Is there any simpler way?

例如：123会给出

231
321
312
132
213
123

类似地，112计划将给予

Similarly for 112 program would give

121
211
211
121
112
112

因此，对于n组元素，排列将为n！
元素中有重复项，会减少，
我问我怎样才能删除那些重复的集合。 （重复置换排列arr []）

So, for n-set of elements , permutations will be of n! With duplicates in elements, would decrease tht, I'm asking how can i remove those duplicate sets. (duplicate set of permutation arr[])

推荐答案

如果可以首先对词素进行排序，那么你的词汇就可以了排列。包括为int数组执行的算法，可以轻松修改为字符串。

If it is acceptable to first sort the elements lexically, then you can your lexical permutation. Including an algorithm which does it for an array of int, easily modifiable to strings.

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]一起使用

Using this with [1,2,3] you get

[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]开始，您不再获得排列（与上面的示例相比）。

Since the method retunes the "next" permutation in lexicographically order it is important that the elements are ordered. Starting with [3, 2, 1] you get no more permutations (compare to example above).

这篇关于获取int []的排列删除重复集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！