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

2022-01-10 00:00:00 permutation duplicates integer java

我有一个整数数组1<=N<=100，我怎样才能得到这个数组的排列?数组可能包含重复，因此生成的排列集可能是重复的，因此需要获取所有不重复的排列.

I have an array 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，因此将它们转换为字符串会破坏整数.
  • 我可以获得所有带有重复项的排列，包括，对于删除重复项的最终排列组，必须相互检查才能删除重复项左右，这是一个繁重的过程.
  • I've found lot of snippets which would convert the int[] to string and perform permutations and printout, but as I hv here is integers of range 1<=N<=100, so converting them into string would spoil integer.
  • I can get all permutations with duplicates including, for final set of permutations where duplicates are removed have to check with each other to remove a duplicate or so, it so heavy process.

有没有更简单的方法?

例如，123 会给出:

231
321
312
132
213
123

112 程序同样会给出:

121
211
211
121
112
112

因此，对于 n 元素集，排列将是 n!如果元素中有重复项，则会减少 tht.我在问如何删除那些重复的集合.(重复排列 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] 你会得到

with [1,1,3] you instead get

[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).

相关文章