問題描述
我有一個整數數組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 range1<=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).
這篇關于獲取 int[] 的排列刪除重復集的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！