s*******n
发帖数: 97 | 1 string permutation，怎么处理重复字母？ | l*****a
发帖数: 14598 | 2 1) sort
2) get permutation
【在 s*******n 的大作中提到】
: 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 的大作中提到】
: 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
ｎｅａｔ
【在 w*******s 的大作中提到】
: 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 的大作中提到】
: 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';
|
|
