e****e
发帖数: 418 | 1 抛砖引玉, any suggestion is welcome!
The idea is to sort the elements to be permuted if they are not already
sorted and restore to their original values after their permutation. Before
we go to next level, check to see if the num on the next level is the same
as current num. If yes, skip the next level.
public void permute(int[] perm, int level){
if ( level == perm.length ) {
System.out.println( new String( perm ) );
return;
}
int[] toBePermuted = null;
if ( !isSorted( perm, level ) ) {
toBePermuted = new int[perm.length-level];
for ( int i = level ; i < perm.length; i++ )
toBePermuted[i-level] = perm[i];
Arrays.sort( perm, level, perm.length );
}
for ( int i = level; i < perm.length; ) {
if ( level != i )
swap( perm, level, i );
permute( perm, level+1 );
if ( level != i )
swap( perm, level, i );
i++;
while ( i < perm.length && perm[i-1] == perm[i] )
i++;
}
if ( toBePermuted != null ) {
for ( int i = level ; i < perm.length; i++ )
perm[i] = toBePermuted[i-level];
}
}
private boolean isSorted( int[] num, int level ) {
for ( int i = level+1; i < num.length; i++ ) {
if ( num[i-1] > num[i] )
return false;
}
return true;
}
private void swap(int[] num, int i, int j) {...} |
l*****a
发帖数: 14598 | 2 太累赘
Arrays.sort()有必要这么多参数吗？
什么sort前面要加一段isSorted？第一次见到，不过不能说没有道理
Before
【在 e****e 的大作中提到】
: 抛砖引玉, any suggestion is welcome!
: The idea is to sort the elements to be permuted if they are not already
: sorted and restore to their original values after their permutation. Before
: we go to next level, check to see if the num on the next level is the same
: as current num. If yes, skip the next level.
: public void permute(int[] perm, int level){
: if ( level == perm.length ) {
: System.out.println( new String( perm ) );
: return;
: }
|
e****e
发帖数: 418 | 3 想不出简单的，所以标题是抛砖引玉。在for loop之前的sort code只是针对从index从
level开始之后的元素如果不是sorted, 就排序, 因为之前的元素已经permuted处理过
了,它们就不是关注(排序)的对象了.
【在 l*****a 的大作中提到】
: 太累赘
: Arrays.sort()有必要这么多参数吗？
: 什么sort前面要加一段isSorted？第一次见到，不过不能说没有道理
:
: Before
|
s****0
发帖数: 117 | 4 这个不是更优吗？
http://en.wikipedia.org/wiki/Permutation
5.2.1 Random generation of permutations
5.2.2 Generation in lexicographic order
5.2.3 Generation with minimal changes |
e****e
发帖数: 418 | 5 - 5.2.1 Random generation of permutations
一个是permutation，一个是random shuffle. 不是一回事吧！
- 5.2.2 Generation in lexicographic order
next permutation这个思路挺好,可以处理duplicates的情况.但是找next
permuatation的时间复杂度是O(n),总的时间复杂度是O(n*n!).
- 5.2.3 Generation with minimal changes
就是上面代码的思路，上面代码还有处理duplicates的逻辑在里面。
谢谢你的suggestion, snow20. Appreciate it!
【在 s****0 的大作中提到】
: 这个不是更优吗？
: http://en.wikipedia.org/wiki/Permutation
: 5.2.1 Random generation of permutations
: 5.2.2 Generation in lexicographic order
: 5.2.3 Generation with minimal changes
|
p*****2
发帖数: 21240 | 6 练练ruby
a=[1,1,3]
p a.permutation.to_a.uniq |
e****e
发帖数: 418 | 7 once again, er ye's code opens up my eyes.
【在 p*****2 的大作中提到】
: 练练ruby
: a=[1,1,3]
: p a.permutation.to_a.uniq
|
f*****7
发帖数: 92 | 8 我个人不喜欢swap的方法，自己没法理解
排序，然后跳过重复元素
希望能帮上你
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(), num.end());
int len = num.size();
int* path = (int*) malloc(sizeof(int) * len);
bool* visited = (bool*) malloc(sizeof(int) * len);
memset(visited, false, sizeof(bool) * len);
vector > bigList;
int level = 0;
permutation(num, path, visited, level, bigList);
free(path);
path = NULL;
free(visited);
visited = NULL;
return bigList;
}
void permutation(vector& num, int* path, bool* visited, int level,
vector >& bigList)
{
if (level == num.size())
{
//find a permutation
vector smallList;
for(int i = 0; i < level; i++)
{
smallList.push_back(path[i]);
}
bigList.push_back(smallList);
}
else
{
for(int i = 0; i < num.size();)
{
if (false == visited[i])
{
path[level] = num[i];
visited[i] = true;
permutation(num, path, visited, level + 1, bigList);
//backtracking
visited[i] = false;
//skip duplicates
while(i < num.size() && num[i] == path[level])
{
i++;
}
}
else
{
i++;
}
}
}
}
}; |
e****e
发帖数: 418 | 9 feiw217, 谢谢你贴出解法。这个解法空间和时间上都不是最优。swap的方法表面是看
是swap, 其实是recursion的思路.再次感谢你的解法。
【在 f*****7 的大作中提到】
: 我个人不喜欢swap的方法，自己没法理解
: 排序，然后跳过重复元素
: 希望能帮上你
: class Solution {
: public:
: vector > permuteUnique(vector &num) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: sort(num.begin(), num.end());
: int len = num.size();
|
p*****2
发帖数: 21240 | 10
大牛现在复习到什么程度了？
【在 e****e 的大作中提到】
: feiw217, 谢谢你贴出解法。这个解法空间和时间上都不是最优。swap的方法表面是看
: 是swap, 其实是recursion的思路.再次感谢你的解法。
|
|
|
e****e
发帖数: 418 | 11 二爷又取笑了。在重新做高频题，争取做到多想想看有没有其他解法，找到最优解...
【在 p*****2 的大作中提到】
:
: 大牛现在复习到什么程度了？
|
p*****2
发帖数: 21240 | 12
好。精益求精。准备什么时候出手？
【在 e****e 的大作中提到】
: 二爷又取笑了。在重新做高频题，争取做到多想想看有没有其他解法，找到最优解...
|
e****e
发帖数: 418 | 13 尽快吧。其实我还挺enjoy准备学习的过程。。。
【在 p*****2 的大作中提到】
:
: 好。精益求精。准备什么时候出手？
|
s****0
发帖数: 117 | 14 我觉得你没有理解人家的思路。这里是我的Java实现，仅供参考。
//- 5.2.3 Generation with minimal changes
package mylib;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Perm implements Iterable>, Iterator> {
final int n;
final int pos[];
final Integer perm[];
final boolean dir[];
final T[] data;
int cnt;
public Perm(List data) {
this.n = data.size();
pos = new int[n];
perm = new Integer[n];
dir = new boolean[n];
@SuppressWarnings("unchecked")
T[] d2 = (T[]) data.toArray();
this.data = d2;
}
@Override
public Iterator> iterator() {
cnt = 1;
for (int i = 0; i < n; i++) {
perm[i] = i;
pos[i] = i;
cnt *= i + 1;
dir[i] = false;
}
return this;
}
@Override
public boolean hasNext() {
return ((cnt--) > 0);
}
@Override
public List next() {
List res = new ArrayList();
for (int i = 0; i < n; i++) {
res.add(data[perm[i]]);
}
for (int v = n - 1; v >= 0; v--) {
int i = pos[v];
int j = (dir[perm[i]] ? i + 1 : i - 1);
if (j < 0 || j >= n || !(v > perm[j]))
continue;
int tmp = perm[i];
perm[i] = perm[j];
perm[j] = tmp;
pos[perm[i]] = i;
pos[perm[j]] = j;
for (int k = v + 1; k < n; k++)
dir[k] = !dir[k];
break;
}
return res;
}
@Override
public void remove() {
// throw new NotImplementedError();
throw new UnsupportedOperationException();
}
public static void main(String[] args) {
List data = java.util.Arrays.asList("1", "2", "3", "4");
Perm tt = new Perm(data);
for (List v : tt) {
System.out.println(v);
}
}
} |
e****e
发帖数: 418 | 15 当时没有仔细看，以为和recursion是一回事。Johnson–Trotter算法确实很巧妙，多
谢你的代码，收益非浅。
【在 s****0 的大作中提到】
: 我觉得你没有理解人家的思路。这里是我的Java实现，仅供参考。
: //- 5.2.3 Generation with minimal changes
: package mylib;
: import java.util.ArrayList;
: import java.util.Iterator;
: import java.util.List;
: public class Perm implements Iterable>, Iterator> {
: final int n;
: final int pos[];
: final Integer perm[];
|
j*****y
发帖数: 1071 | 16 感觉是不是和 通过求 next permutation的思路差不多阿？
【在 s****0 的大作中提到】
: 我觉得你没有理解人家的思路。这里是我的Java实现，仅供参考。
: //- 5.2.3 Generation with minimal changes
: package mylib;
: import java.util.ArrayList;
: import java.util.Iterator;
: import java.util.List;
: public class Perm implements Iterable>, Iterator> {
: final int n;
: final int pos[];
: final Integer perm[];
|
e****e
发帖数: 418 | 17 我觉得不一样，Johnason算法每次交换相邻的元素一次。
【在 j*****y 的大作中提到】
: 感觉是不是和 通过求 next permutation的思路差不多阿？
|
