Cracking Coding Interview - 8.7 Permutation Without Dups

1
2
3
4

permute(abcd) = a 插入到 permute(bcd) 结果的各个插入点
permute(bcd) = b 插入到 permute(cd) 结果的各个插入点
permute(cd) = c 插入到 permute(d) 结果的各个插入点
permute(d) = d

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public List<String> permute(String str) {
  List<String> result = new ArrayList<>();
  if (str.length() == 1) {
    result.add(str)
    return result;
  }
  char c = str.charAt(0);
  List<String> permutations = permute(str.subString(1));
  for (String permutation : permutations) {
    for (int i = 0; i <= permutation.length(); i++) {
      result.add(insert(permutation, i, c));
    }
  }
}

private String insert(String str, int index, char c) {
  if (index == 0) {
    return c + str;
  }
  if (index == str.length()) {
    return str + c;
  }
  return str.subString(0, index - 1) 
         + c 
         + str.subString(index, str.length());
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

permute(abcd) =   a + permute(bcd)
                + b + permute(acd)
                + c + permute(abd)
                + d + permute(abc)
permute(bcd)  =   b + permute(cd)
                + c + permute(bd)
                + d + permute(bc)
permute(cd)   =   c + permute(d)
                + d + permute(c)
permute(c)    = c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public List<String> permute(String str) {
  List<String> result = new ArrayList<>();
  if (str.length() == 1) {
    result.add(str);
    return result;
  }
  for (int i = 0; i < str.length(); i++) {
    char initial = str.charAt(i);
    String remaining = deleteChar(str, i);
    List<String> remainingPermutations = permute(remaining);
    for (String remainingPermutation : remainingPermutations) {
      result.add(initial + remainingPermutation);
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

P( , abc)
  P(a, bc)
    P(ab, c)
      P(abc, ) <-
    P(ac, b)
      P(acb, ) <-
  P(b, ac)
    P(ba, c)
      P(bac, ) <-
    P(bc, a)
      P(bca, ) <-
  P(c, ab)
    P(ca, b)
      P(cab, ) <-
    P(cb, a)
      P(cba, ) <-

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public List<String> permute(String str) {
  List<String> result = new ArrayList<>();
  permute(new StringBuilder(), new StringBuilder(str), result);
  return result;
}

public void permute(StringBuilder prefix, StringBuilder post, List<String> permutations) {
  if (post.length() == 0) {
    permutations.add(prefix.toString());
    return;
  }
  for (int i = 0; i < post.length(); i++) {
    char c = post.charAt(i);
    prefix.append(c);
    post.delete(i);
    
    permute(prefix, post, permutations);
    
    prefix.delete(prefix.length() - 1);
    post.insert(c, i);
  }
}