按字典顺序打印所有排列

Question

我想按字典顺序打印字符串的所有排列.我写这段代码:

void permute(char *a, int i, int n) {
   if (i == (n-1)) printf("\"%s\"\n", a);
   else {
       for (int j = i; j < n; j++) {
           swap((a+i), (a+j));
           permute(a, i+1, n);
           swap((a+i), (a+j));
       }
   }
}

我有例如字符串abc,所以我希望按照左栏中的字典顺序接收所有排列,但我的结果与右列相同.

"abc"                   "abc"
"acb"                   "acb"
"bac"                   "bac"
"bca"                   "bca"
"cab"            <
"cba"                   "cba"
                 >      "cab"

有人可以帮我弄这个吗？我看到了一些算法,但看起来很难.我想我可以在数组中保存所有生成的字符串然后对这个数组进行排序,但是我不能写这个(我是C语言的初学者).

Answer 1

在C.

在geeksforgeeks上有一个非常直接的算法描述(加上实现):

给定一个字符串,按排序顺序打印它的所有排列.例如,如果输入字符串是"ABC",则输出应为"ABC,ACB,BAC,BCA,CAB,CBA".

我们已经讨论过在这篇文章中打印所有排列的程序,但是在这里我们必须按递增的顺序打印排列.

以下是按字典顺序打印排列的步骤

1. 以非递减顺序对给定字符串进行排序并打印它.第一个排列始终是以非递减顺序排序的字符串.

2. 开始生成下一个更高的排列.这样做直到下一个更高的排列是不可能的.如果我们达到所有字符按非递增顺序排序的排列,则该排列是最后的排列.

生成下一个更高排列的步骤:
1.取出先前打印的排列并找到其中最右边的字符,该字符小于其下一个字符.让我们将这个角色称为"第一个角色".

2. 现在找到"第一个角色"的天花板.天花板是"第一个字符"右边的最小字符,大于"第一个字符".让我们将ceil字符称为"第二个字符".

3. 交换上面两步中找到的两个字符.

4. 在"第一个字符"的原始索引之后对子字符串(以非递减顺序)排序.

我在下面重新实现了它:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void swap(char* left, char* right)
{
    char temp = *left;
    *left = *right;
    *right = temp;
}
int compare (const void * a, const void * b)
{
  return ( *(char*)a - *(char*)b );
}
void PrintSortedPermutations(char* inStr)
{
    // Re-implementation of algorithm described here:
    // http://www.geeksforgeeks.org/lexicographic-permutations-of-string/
    int strSize = strlen(inStr);
    // 0. Ensure input container is sorted
    qsort(inStr, strSize, sizeof(char), compare);


    int largerPermFound = 1;
    do{
        // 1. Print next permutation
        printf("%s\n", inStr);
        // 2. Find rightmost char that is smaller than char to its right
        int i;
        for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){}

        // if we couldn't find one, we're finished, else we can swap somewhere
        if (i > -1)
        {
            // 3 find character at index j such that 
            // inStr[j] = min(inStr[k]) && inStr[k] > inStr[i] for all k > i
            int j = i+1;
            int k;
            for(k=j;k<strSize && inStr[k];++k)
            {
                if (inStr[k] > inStr[i] && inStr[k] < inStr[j])
                    j = k;
            }

            // 3. Swap chars at i and j
            swap(&inStr[i], &inStr[j]);

            // 4. Sort string to the right of i
            qsort(inStr+i+1, strSize-i-1, sizeof(char), compare);
        }
        else
        {
            largerPermFound = 0;
        }
    }while(largerPermFound);
}

int main(void) {
    char str[] = "abc";

    PrintSortedPermutations(str);
    return 0;
}

产量

abc
acb
bac
bca
cab
cba

现场演示

在C++中

std::next_permutation从<algorithm>库中为您完成此操作,只需确保您首先对容器进行排序:

返回值

如果函数可以将对象重新排列为lexicographicaly更大的排列,则为true.否则,该函数返回false以指示排列不大于前一个,但最低可能(按升序排序).

例如:

std::string myStr = "abc";
std::stable_sort(std::begin(myStr), std::end(myStr));
do {
    for(auto&& element : myStr)
        std::cout << element << " ";
    std::cout << std::endl;
} while (std::next_permutation(std::begin(myStr), std::end(myStr)));

输出:

abc
acb
bac
bca
cab
cba

现场演示

Answer 2

由于您是初学者，所以我假设您要使用递归版本。

这是两个解决方案。

解决方案1）

由于您想按词典顺序排列，因此您所需要做的就是在需要时选择下一个最小的可能。而已！

例如，这是python中的递归版本

def permute(done, remaining):
  if not remaining:
    print done
    return

  sorted_rem = sorted(remaining)
  l = len(sorted_rem)

  for i in xrange(0, l):
    c = sorted_rem[i]

    # Move to c to done portion.
    done.append(c)
    remaining.remove(c)

    # Permute the remaining
    permute(done, remaining)

    # Put c back.
    remaining.append(c)
    # Remove from done.
    del done[-1]

permute([], [1,2,3,4])

而已。

解决方案2）

尽管解决方案1可行且易于理解，但我怀疑我们可能会通过排序浪费一些时间。该解决方案更接近您所拥有的。

递归基本上是变相的数学归纳法，这种思维方式对于理解如何编写递归程序非常有用。

例如，假设您的置换方法始终按字典顺序构造置换。

这是一个递归版本，具有该假设，请阅读注释以了解发生了什么。

// By induction assumption, permute(a, i, n)
// goes through all the permutations of a[i], ..., a[n-1]
// in lexicographic order, by modifying a itself.
void permute(char *a, int i, int n) {
    if (i == (n-1)) {
       printf("%s\n", a);
      return;
    }

    int j;
    // We pick the n-i posibilities for the position a+i, then recursively
    // compute the permutations of a[i+1], ..., a[n-1]
    // So first pick the smallest possible for a+i, recurse.
    // Then the next possible for a+i, then recurse etc.

    for (j = i; j < n; j++) {
      permute(a, i+1, n);
      // By our induction assumption, at this point, 
      // a[i+1], a[i+2], .., a[n-1]
      // must be the lexicographically the largest possible!

      // So now reverse that portion.
      reverse(a+i+1, a+n-1);

      // Now we need to pick the lexicographically next element for
      // position a+i. This is nothing but the element which is just
      // larger than the current a+i.

      int k = i+1;
      while(k < n && a[i] > a[k]) {
        k++;
      }

      if (k >= n) {
        continue;
      }
      // Choose the next value for a+i.
      swap(a+i, a+k);
    }
    // Notice that the portion a[i+1], ..., a[n-1]  is sorted increasing.
    // when the loop exits. Also a[i] will be the largest element.
    // We need to reverse so that a[i], .., a[n-1] is the lexicographically
    // largest permutation to  maintain the induction (recursion) assumption.
    reverse(a+i+1, a+n-1);
}

请注意，此版本与迭代版本（由其他版本和下面的部分指定）之间的相似之处，其中您在末尾反转了一个块，并交换了两个元素。

顺便说一句，按字典顺序生成排列的通用迭代算法是Narayana Pandita算法，其他人提到过，但没有提到。

看到此链接：http : //en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

这就是C ++的std :: next和其他许多库使用的东西。

即使存在重复的元素，该算法也可以使用，并且实际上可以用来生成组合！（用零和一初始化您的数组）。