数组中字符的排列

我输入一个字符数组，并希望获得该数组的所有可能组合作为输出。例如，如果我输入字符数组=“A，B，C”，我想在这种形式的输出：数组中字符的排列

a b c, 
a c b, 
b a c, 
b c a, 
c a b, 
c b a

并且类似地，如果我输入4个字符，我想要得到24个组合。我为此做了一个代码，但它返回的组合只是输入字符数量的两倍。也就是说，如果我输入3个字符（这是正确的），代码将返回6个组合，但是如果我输入4个字符，它将只返回8个可能的组合，而不是24个组合。我的代码如下：

#include <iostream> 
#include<string.h> 
#include<stdio.h> 
using std::cout; 
void getCombination(char *); 

int main() 
{ 
    const int maxStringSize = 26; 
    char thisString[maxStringSize]; 
    cout<<"Enter String = "; 
    gets (thisString); 
    getCombination(thisString); 
    return 0; 
} 

void getCombination(char *thisString) 
{ 
    int stringSize=strlen(thisString); 
    for(int i = 0; i<stringSize; i++) 
    { 
     for(int j = 0; j<stringSize; j++) 
     { 
      cout<<thisString[(i+j)%stringSize]; 
     } 
     cout<<"\n"; 
     for(int k = stringSize-1; k>=0; k--) 
     { 
      cout<<thisString[(i+k)%stringSize]; 
     } 
    cout<<"\n"; 
    } 
}

来源

2011-06-18 Qasim

[在一个数组获取所有排列]的可能重复（http://stackoverflow.com/questions/1272828/getting-all-the-permutations-in-an-array） –

@Bo Persson的：可能的：但是不同的语言。 – Johnsyweb

评价关于术语：这些被称为排列不组合。

那是因为你只看着由形成排列：

采摘的第一个字母和
把剩下的才能或
把其余按相反的顺序

特别是，你永远不可能从abcd这样形成acbd。

我建议尝试递归解决方案，而不是第一遍（选取第一个字母，然后查看其余所有排列）。

然后从递归解决方案中，您可以制定一个解决方案，使用数据结构（如堆栈），如果您担心由于递归调用过多导致堆栈溢出。

来源

2011-06-18 06:14:06 trutheality

http://www.sgi.com/tech/stl/next_permutation.html

的std :: next_permutation应该可以帮助你去

来源

2011-06-18 06:18:30

我是C++新手，所以我没有得到任何答案。你想简化它吗？ – Qasim

链接中有一个例子，documentaiton非常简单;）参见下面的一个实际例子 –

为什么你的代码没有？

您的代码会产生2次排列，因为这就是您正在做的事情。您正在选择前缀，然后按照相反的顺序打印字符串，即每个前缀有两个输出。总数= n * 2。（这样你怎么可能打印所有的排列？）

解决方案！

你需要的是std :: next_permutation。请记住，在将数组传递给next_permutation之前，先对数组进行排序，然后按递增顺序生成排列，具体来说就是您需要的（根据您的示例）。

您可以阅读关于产生正确输出的递归实现以及如何在C++ here中实现next_permutation。

来源

2011-06-18 06:38:41

这是另一个演示：http://ideone.com/DvhHN – Johnsyweb

@Johnsyweb：谢谢，这几乎总结了:)。 –

我想这是可以做到这样：

void swap(char &a, char &b) { 
char c=a; 
a = b; 
b = c; 
} 


void get_Combination(string word, int d) { 
if (d == word.size()) { 
    cout<<word<<endl; 
    return; 
} 

for (int i=d; i< word.size(); ++i) { 
    swap(word[i],word[d]); 
    get_combination(word, d+1); 
    swap(word[i],word[d]); 
} 
}

说明： ü通过调用get_combination启动（字，0）。现在要查找字符串的所有排列，每个位置上的每个字符应该以一个或其他排列出现在第一个位置。因此，我们从d = 0开始，并将每个字符交换到d中字符结尾。在第一个字符就位的情况下，我们通过调用get_combination（word，d + 1）重复第二个字符开始的过程。还要注意第二个交换，它需要将初始交换的字符恢复到其原始位置，然后用位置d处的字符交换下一个字符。

例子：

给出字符串ABC，这里是递归树，GC = get_combination

gc("abc",0) 

    gc(abc,1) 

     gc(abc,2) 

     cout<<"abc" 

     gc(acb,2) 

     cout<<"acb" 

    gc(bac,1) 

     gc(bac,2) 

     cout<<"bac" 

     gc(bca,2) 

     cout<<"bca" 

    gc(cba,1) 

     gc(cba,2) 

     cout<<"cba" 

     gc(cab,2) 

     cout<<"cab"

来源

2011-06-18 07:44:12

您可以在标准库的算法部分使用std::next_permutation做到这一点。举例来看下面的代码片段。请注意，我首先排序theString，因为这是next_permutation要求查找所有组合。

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    std::string theString = "abc"; 

    std::sort(theString.begin(), theString.end()); 

    do 
    { 
     std::cout << theString << std::endl; 
    } 
    while (std::next_permutation(theString.begin(), theString.end())); 

    return 0; 
}

来源

2011-06-18 10:22:11 Node

数组中字符的排列

回答

相关问题