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

Question

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

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

有没有更简单的方法？

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

Answer 2

您可以使用 Set 而不是整数数组，它可以自动删除您的重复项。

编辑： @allingeek 给我一个想法。不仅仅是实现您自己的设置 您可以在 int 上编写一个包装器并覆盖您的 equals 和 hashcode 方法，找到您的排列相等的方式。也许按顺序使用数字和“Effective Java”中给出的其他建议（用于 equals 和 hashcode 实现以避免错误）。它可以为您提供更好的方法来在 设置。不仅仅是像我一开始所说的那样使用表达式语言。

Answer 3

您需要数组的所有非重复排列。假设每个数组条目都是唯一的 Factorial(array.length)，它们的数量很快就会变得难以计算。但假设您想枚举它们，最简单的方法是执行以下操作：

您的问题基本上是字母表的选择问题（1 <= N <= 100）。如果您想选择其中的 5 个或 500 个，都没关系，您想选择某个数字，称之为 x。想想您想要从中选择的独特元素，以及那些您不想重复的元素（这可能是您的字母表的适当子集，也可能不是）。将这些元素排成一行。该行的长度为n。现在，可以如下解决枚举 x 的选择的选择问题。想象一个 n 位数字，它只能包含 nx 个零。要获得这个 x 级数字，只需从 0 开始，枚举最多 2**n 的所有可能数字，仅选择那些恰好具有 x 个 1（和 nx 个零）的数字。然后，这些 1 从字母表的 n 个位置中选择 x 个位置，每个 x 级数字都会为您选择一个排列。

如果有人知道一种优化方法，这样您就不必计算出所有非 x 级的优化，请说出来。
编辑：
答案似乎就在这里

Answer 4

删除重复元素的最简单方法是将内容添加到 Set 不允许重复，然后将 Set 添加回 ArrayList 如下所示。

ArrayList<String>al=new ArrayList<String>();

al.add(String.valueOf(arr[0]));  //Just as an example.

HashSet hs = new HashSet();
hs.addAll(al);
al.clear();
al.addAll(hs);

Answer 5

1. 对数组进行排序。
2. 使用嵌套循环，其中外循环迭代数组中的每个元素。如果下一个元素与上一个元素具有相同的值，则跳过。然后，内部循环将该元素放置在列表中的每个位置。在每个循环上保存排列。

这将生成排列并跳过重复的排列。

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;
}

编辑：实际上我认为这需要进行更多调整以捕获生成重复项的最后几种情况。这就是在其相同值旁边插入重复元素的地方。我已经适当地更改了代码。