中包含字母排列：如何删除重复的排列？ [英] Permutation of String letters: How to remove repeated permutations?

问题描述

下面是一个标准的功能，以打印一个字符串的字符的排列：

Here is a standard function to print the permutations of characters of a string:

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j < n; j++) //check till end of string
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

它工作正常，但有一个问题，它也会打印一些重复的排列，exapmle：

It works fine but there is a problem, it also prints some duplicate permutations, exapmle:

如果字符串为AAB

输出：

AAB
ABA
AAB
ABA
BAA
BAA

这是具有3个重复的条目。

This is having 3 duplicate entries as well.

能否有一种方法，以prevent这种情况发生？

Can there be a way to prevent this to happen?

-

感谢

阿洛克氪。

推荐答案

做笔记，你换previously其中碳化的：

Take notes which chars you swapped previously:

 char was[256];
 /*
 for(j = 0; j <= 255; j++)
    was[j] = 0;
 */
 bzero(was, 256);
 for (j = i; j <= n; j++)
 {
    if (!was[*(a+j)]) {
      swap((a+i), (a+j));
      permute(a, i+1, n);
      swap((a+i), (a+j)); //backtrack
      was[*(a+j)] = 1;
    }
 }

这已经是最快的国家之一，从目前的条目，在AAAABBBCCD（100环）的一些基准测试：

This has to be the fastest one from the entries so far, some benchmark on a "AAAABBBCCD" (100 loops):

native C             - real    0m0.547s
STL next_permutation - real    0m2.141s

这篇关于中包含字母排列：如何删除重复的排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！