按字典顺序打印所有排列 [英] Print all permutation in lexicographic order

查看：42
本文介绍了按字典顺序打印所有排列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

void permute(char *a, int i, int n) {if (i == (n-1)) printf("\"%s\"\n", a);别的 {for (int j = i; j

让我们以字符串 abc 为例，我想像左列一样按字典顺序接收所有排列，但我在右列中得到了结果.

"abc" "abc""acb" "acb"巴克"巴克""bca" "bca"驾驶室"<"cba" "cba">出租车"

有人可以帮我解决这个问题吗?我看到了一些算法，但它们看起来很难.我想我可以将所有生成的字符串保存在一个数组中，然后对这个数组进行排序，但我不会写这个(我是 C 的初学者).

解决方案

In C

在 geeksforgeeks 中有一个非常简单的算法描述(加上实现):

<块引用>

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

我们在这篇文章中讨论了一个打印所有排列的程序，但在这里我们必须按升序打印排列.

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

  1. 将给定的字符串按非降序排序并打印出来.第一个排列始终是按非降序排序的字符串.

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

生成下一个更高排列的步骤:
1. 取之前打印的排列，找到其中最右边的一个字符，比它的下一个字符小.让我们打电话这个字符作为第一个字符".

  1. 现在找到第一个字符"的上限.天花板是第一个字符"右侧的最小字符，较大而不是第一个字符".让我们称 ceil 字符为second"字符’.

  2. 交换上述 2 个步骤中找到的两个字符.

  3. 在'第一个字符'的原始索引之后对子字符串进行排序(非降序).

我在下面重新实现了它:

#include #include #include 无效交换(字符*左，字符*右){字符温度 = *左；*左 = *右;*右 = 温度；}int compare (const void * a, const void * b){返回 ( *(char*)a - *(char*)b );}void PrintSortedPermutations(char* inStr){//重新实现这里描述的算法://http://www.geeksforgeeks.org/lexicographic-permutations-of-string/int strSize = strlen(inStr);//0. 确保输入容器已排序qsort(inStr, strSize, sizeof(char), compare);整数更大的PermFound = 1;做{//1. 打印下一个排列printf("%s\n", inStr);//2. 找到最右边的小于其右边的字符的字符国际我;for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){}//如果我们找不到，我们就完成了，否则我们可以换一个地方如果 (i > -1){//3 在索引 j 处找到字符，使得//inStr[j] = min(inStr[k]) &&inStr[k] >inStr[i] 对于所有 k >一世int j = i+1;国际 k;for(k=j;k<strSize && inStr[k];++k){如果 (inStr[k] > inStr[i] && inStr[k] < inStr[j])j = k;}//3. 在 i 和 j 处交换字符交换(&inStr[i], &inStr[j]);//4. 将字符串排序到 i 的右边qsort(inStr+i+1, strSize-i-1, sizeof(char), compare);}别的{较大的PermFound = 0;}}while(largerPermFound);}int main(void) {char str[] = "abc";PrintSortedPermutations(str);返回0；}

输出

<块引用>

abc
acb
bac
bca
cab
cba

现场演示

<小时>

在 C++ 中

std::next_permutation 来自 库会为你做这件事，只要确保你先对你的容器进行排序:

<块引用>

返回值

如果函数可以按字典顺序重新排列对象，则为真更大的排列.否则，该函数返回 false 以指示排列不大于之前的，而是最低的可能(按升序排序).

例如:

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

输出:

<块引用>

a b c
a c b
b a c
b c a
c a b
c b a

现场演示

I want to print all permutation of string in lexicographic order. I wrote this code:

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));
       }
   }
}

Let's take for example string abc, I want to receive all permutation in lexicographic order as in the left column, but I have result as in the right column.

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

Can someone help me with this? I saw some algorithms, but they look difficult. I think I can save all generated strings in an array and then sort this array, but I cannot write this (I'm a beginner in C).

解决方案

In C

There's a pretty straightforward description of an algorithm (plus implementation) at geeksforgeeks:

Given a string, print all permutations of it in sorted order. For example, if the input string is "ABC", then output should be "ABC, ACB, BAC, BCA, CAB, CBA".

We have discussed a program to print all permutations in this post, but here we must print the permutations in increasing order.

Following are the steps to print the permutations lexicographic-ally

  1. Sort the given string in non-decreasing order and print it. The first permutation is always the string sorted in non-decreasing order.

  2. Start generating next higher permutation. Do it until next higher permutation is not possible. If we reach a permutation where all characters are sorted in non-increasing order, then that permutation is the last permutation.

Steps to generate the next higher permutation:
1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.

  1. Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.

  2. Swap the two characters found in above 2 steps.

  3. Sort the substring (in non-decreasing order) after the original index of ‘first character’.

I've re-implemented it below:

#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;
}

Output

abc
acb
bac
bca
cab
cba

Live Demo

In C++

std::next_permutation from the <algorithm> library will do this for you, just make sure you sort your container first:

Return value

true if the function could rearrange the object as a lexicographicaly greater permutation. Otherwise, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

For example:

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)));

Output:

a b c
a c b
b a c
b c a
c a b
c b a

Live Demo

这篇关于按字典顺序打印所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆