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

Question

我有一个整数数组 1<=N<=100 , 我怎样才能得到这个数组的排列？数组可能包含重复项，因此排列结果集可能重复，因此需要获取所有非重复排列。

• 我发现了很多可以转换 int[] 的片段串起来并执行排列和打印输出，但正如我所言，这里是范围为 1<=N<=100 的整数，因此将它们转换为字符串会破坏整数。
• 我可以获得所有包含重复项的排列，包括对于删除重复项的最后一组排列，必须相互检查以删除重复项，这是一个非常繁重的过程。

有没有更简单的方法？

例如，123会给出:

231
321
312
132
213
123

同样适用于 112程序会给出:

121
211
211
121
112
112

因此，对于 n - 元素集，排列将为 n!对于元素中的重复项，会减少 tht。我在问如何删除那些重复的集合。 (重复排列 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] 开始，您不再获得排列(与上面的示例相比)。