是不是沃尔玛现在ATM也不可以冲BB了？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

是不是沃尔玛现在ATM也不可以冲BB了？

是不是沃尔玛现在ATM也不可以冲BB了？# Money - 海外理财

e*e2014-07-01 07:07

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) {...}

C*42014-07-01 07:07

2 楼

晚上带4张灰香草去ATM充值，全部失败。。。是不是不让充值了？
换MO？

l*a2014-07-01 07:07

3 楼

太累赘
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;
: }

h*s2014-07-01 07:07

4 楼

mo也不行了。其实是灰香草不行了。

【在 C*4 的大作中提到】

: 晚上带4张灰香草去ATM充值，全部失败。。。是不是不让充值了？
: 换MO？

e*e2014-07-01 07:07

5 楼

想不出简单的，所以标题是抛砖引玉。在for loop之前的sort code只是针对从index从
level开始之后的元素如果不是sorted, 就排序, 因为之前的元素已经permuted处理过
了,它们就不是关注(排序)的对象了.

【在 l*****a 的大作中提到】

: 太累赘
: Arrays.sort()有必要这么多参数吗？
: 什么sort前面要加一段isSorted？第一次见到，不过不能说没有道理
:
: Before

e*e2014-07-01 07:07

6 楼

Deal gone bad from the bank that is issuing vanilla series card.
RV got kicked out by CVS
Vanilla got kicked out by BB/walmart
other cards from staple/grocery are still alive. I just load both of them to
BB tonight at boston area. Sweet

【在 h****s 的大作中提到】

: mo也不行了。其实是灰香草不行了。

s*02014-07-01 07:07

7 楼

这个不是更优吗？
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

C*42014-07-01 07:07

8 楼

头大

【在 h****s 的大作中提到】

: mo也不行了。其实是灰香草不行了。

e*e2014-07-01 07:07

9 楼

- 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*22014-07-01 07:07

10 楼

练练ruby
a=[1,1,3]
p a.permutation.to_a.uniq

e*e2014-07-01 07:07

11 楼

once again, er ye's code opens up my eyes.

【在 p*****2 的大作中提到】

: 练练ruby
: a=[1,1,3]
: p a.permutation.to_a.uniq

f*72014-07-01 07:07

12 楼

我个人不喜欢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*e2014-07-01 07:07

13 楼

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*22014-07-01 07:07

14 楼

大牛现在复习到什么程度了？

【在 e****e 的大作中提到】

: feiw217, 谢谢你贴出解法。这个解法空间和时间上都不是最优。swap的方法表面是看
: 是swap, 其实是recursion的思路.再次感谢你的解法。

e*e2014-07-01 07:07

15 楼

二爷又取笑了。在重新做高频题，争取做到多想想看有没有其他解法，找到最优解...

【在 p*****2 的大作中提到】

:
: 大牛现在复习到什么程度了？

p*22014-07-01 07:07

16 楼

好。精益求精。准备什么时候出手？

【在 e****e 的大作中提到】

: 二爷又取笑了。在重新做高频题，争取做到多想想看有没有其他解法，找到最优解...

e*e2014-07-01 07:07

17 楼

尽快吧。其实我还挺enjoy准备学习的过程。。。

【在 p*****2 的大作中提到】

:
: 好。精益求精。准备什么时候出手？

s*02014-07-01 07:07

18 楼

我觉得你没有理解人家的思路。这里是我的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*e2014-07-01 07:07

19 楼

当时没有仔细看，以为和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*y2014-07-01 07:07

20 楼

感觉是不是和通过求 next permutation的思路差不多阿？

【在 s****0 的大作中提到】

e*e2014-07-01 07:07

21 楼

我觉得不一样，Johnason算法每次交换相邻的元素一次。

【在 j*****y 的大作中提到】

: 感觉是不是和通过求 next permutation的思路差不多阿？