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

我有一个整数数组1<=N<=100，如何获得这个数组的排列？数组可能包含重复的排列，所以得到的排列集可能是重复的，所以需要获得所有不重复的排列。

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

有什么更简单的方法吗？

例如，123会给出：

类似地，对于112程序将给出：

因此，对于n-元素集，置换将是n!如果元素中有重复项，则会减少tht。我在问如何删除那些重复的集合。（排列的重复集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方法，找到排列是equals的方式。也许使用"有效Java"中给出的按顺序使用数字和其他建议（对于equals和hashcode实现，以避免错误）。它可以为您提供在集合中查找排列的更好方法。不仅仅是像我刚开始说的那样使用表达语言。

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

你的问题基本上是字母表（1<=N<=100）上的选择问题。无论你想从中选择5个，还是500个，你都想选择一些数字，称之为x。想想你想从其中选择的唯一元素，那些你不想重复的元素（这可能是你字母表的一个子集，也可能不是）。将这些元素排列成一行。这一行的长度是n。现在，枚举其中x的选择的选择问题可以如下解决。想想一个n位的数字，它只能包含n-x个零。要获得这个秩为x的数字，只需从0开始，枚举所有可能的数字，直到2**n，只选择那些恰好有x个1（和n-x个零）的数字。然后，这些1从你的字母表的n个位置中选择x个位置，每个排列x的数字都为你选择一个排列。

如果有人知道一个优化，这样你就不必计算出所有非rank-x的优化，请这样说。编辑：答案似乎就在这里

删除重复元素的最简单方法是将内容添加到不允许重复的Set中，然后将Set back添加到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);

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

这将生成排列以及跳过重复排列。

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

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

相关内容

最新更新

热门标签：