s*******n 发帖数: 97 | 1 string permutation,怎么处理重复字母? | l*****a 发帖数: 14598 | 2 1) sort
2) get permutation
【在 s*******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : string permutation,怎么处理重复字母?
| w*******s 发帖数: 96 | 3 Two implementation. one use sort and one use hash.
//pre: str is sorted.
void PermutationWithDuplicate(char *str, int position)
{
if (position == strlen(str)) {
printf("%s", str);
return;
}
char lastChar = '\0';
for (int i = position; i
{
//skip those character which is duplicated. Since the string is
sorted, it's easy.
if (lastChar == str[i] ) continue;
lastChar = str[i];
swap(str[position], str[i]);
PermutationWithDuplicate(str,position+1);
swap(str[i] , str[position]);
}
}
//pre: str is not sorted and str can't be changed. We can use hash to do
this.
void PermutationWithDuplicateHash(char *str, int position)
{
int HashTable[128] = {0}; //assume ASCII
if (position == strlen(str)) {
printf("%s", str);
return;
}
for (int i = position; i
{
if (HashTable[str[i]) > 0) continue;
else{
HashTable[str[i]] = 1;
}
swap(str[position], str[i]);
PermutationWithDuplicateHash(str,position+1);
swap(str[i] , str[position]);
}
}
main()
{
char str[] = "hello world";
// If duplicated character is allowed, let's sort the string first.
sort(str);
PermutationWithDuplicate(str, 0)
//method 2. Using Hashtable to make a judgement whether it's duplicated
PermutationWithDuplicateHash(str, 0)
} | m****i 发帖数: 650 | 4 It is still a solution without sorting or hashing.
public void permutationRecursive(int[] arr, int index) {
if (arr.length == index) {
for (int i = 0; i < arr.length; ++i) {
System.out.printf("%d", arr[i]);
}
System.out.println();
return;
}
int lastSwap = 0;
for (int i = index; i < arr.length; ++i) {
if (arr[i] == arr[index] && i != index) continue;
if (arr[i] == lastSwap) continue;
lastSwap = arr[i];
swap(arr, i, index);
permutationRecursive(arr, index+1);
swap(arr, i, index);
}
}
private void swap(int[] arr, int i, int j) {
assert (i >= 0 && i >= 0 && i < arr.length && j < arr.length);
if (i != j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {2,3,2,3};
Permutation p = new Permutation();
System.out.println("Permutation");
p.permutationRecursive(arr, 0);
} | s*******n 发帖数: 97 | | H****s 发帖数: 247 | 6 这样不行啊, 如果输入: 1323, 输出有重复的。
我明白你的思路:就是每层循环在一个位置,每个unique字符只出现一次,
但是这只有hash才能保证啊。否则,例子中第二个3的lastSwap是2啊,所以还是有重复
的。
【在 m****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : It is still a solution without sorting or hashing. : public void permutationRecursive(int[] arr, int index) { : if (arr.length == index) { : for (int i = 0; i < arr.length; ++i) { : System.out.printf("%d", arr[i]); : } : System.out.println(); : return; : } : int lastSwap = 0;
| w****x 发帖数: 2483 | | t**r 发帖数: 3428 | 8
neat
【在 w*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Two implementation. one use sort and one use hash. : //pre: str is sorted. : void PermutationWithDuplicate(char *str, int position) : { : if (position == strlen(str)) { : printf("%s", str); : return; : } : : char lastChar = '\0';
| w****o 发帖数: 2260 | 9 测试了一下,用hash的方法PermutationWithDuplicateHash是对的。
另一个先sort,然后只用一个变量lastChar的方法,不正确,会有重复的输出。
【在 w*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Two implementation. one use sort and one use hash. : //pre: str is sorted. : void PermutationWithDuplicate(char *str, int position) : { : if (position == strlen(str)) { : printf("%s", str); : return; : } : : char lastChar = '\0';
|
|