长度k从n个字符的所有排列，在CPP中重复

问题描述

我想知道，如果在CPP中已经有一个实现，可以找到长度为k（1,2,3,4等）的n个字符的所有重复排列。我希望有，但我找不到。

例如，如果 string =（A，B，C，D），我想找到 string ，重复长度 k = 2 。

输出将为：

  AA 
 AB 
 AC 
 AD 
 。 
。 
。 
 DD 
  

总排列数为16.

解决方案

简单的递归解决方案，它会为你工作。

让我先重写你的规范： strong>打印所有具有重复字符的排列

对于大小为n的给定字符串，将有n ^ k个可能的长度字符串长度。这个想法是从一个空的输出字符串开始（我们在下面的代码中称为prefix）。逐个添加所有字符前缀。对于添加的每个字符，通过递归调用length等于length-1来打印所有可能的带有当前前缀的字符串。

  #include< string> 
 #include< iostream> 
 
 
 void print_str（const char *，std :: string，const int，const int）; 
 
 int main（）
 
 {
 
 int lenght = 2; 
 
 char str [] = {'A'，'B'，'C'，'D'}; 
 
 
 
 int n = sizeof str; 
 
 print_str（str，，n，lenght）; //注意：此函数适用于所有情况，不仅仅是上面的情况
 
 return 0; 
 
} 
 
 //主要递归方法打印长度为length的所有可能的字符串
 void print_str（const char str []，std :: string prefix，const int n，const int lenght）
 
 {
 
 if（lenght == 1）
 
 {
 $ b b for（int j = 0; j  
 std :: cout< prefix + str [j]< std :: endl; 
 
} //基本案例：lenght = 1，打印字符串lenght次+剩余字母
 
 else 
 
 {
 
 
 //逐个添加str的所有字符，递归调用lenght等于lenght-1 
 for（int i = 0; i  
 //添加的输入的下一个字符
 print_str（str，prefix + str [i]，n，lenght  -  1）; 
 //lenght减少，因为我们添加了一个新字符
 
} 
 
} 
  pre> 
 
 
这里是上面代码的执行：
 
 
  
 
 
  
 
 
 
  更新：此更新是根据以下规范撰写的。  
 
 $ b b 
  #include< string> 
 #include< iostream> 
 #include< vector> 
 
 void print_str（const char *，std :: string，const int，const int）; 
 std :: vector< std :: string>排列//将包含所有排列的向量排列，
 //如果你希望你可以使用它以后使用，或者你可以使用下面的数组，而不是这个向量的副本。 
 
 int NumberOfPermutations = 0; //此变量保存排列数量
 
 
 
 int main（）
 
 {
 
 int lenght = 3 ; 
 
 char str [] = {'A'，'B'，'C'，'D'}; 
 
 int n = sizeof str; 
 //这里我们遍历所有可能的长度1，2和3 
 for（int k = 1; k  
 {
 
 print_str（str，，n，k）; //注意：此函数适用于所有情况，不仅仅是上面的情况
} 
 
 
 std :: string * permut_array = new std :: string [NumberOfPermutations]; //数组，我们将用它来存储排列在
 
 std :: copy（permutations.begin（），permutations.end（），permut_array）; //这里我们将向量复制到数组
 
 //如果你想你可以使用你的数组打印排列如下
 
 for（int k = 0; k < NumberOfPermutations; k ++）
 
 {
 
 std :: cout< permut_array [k]< std :: endl; 
} 
 
 return 0; 
 
} 
 
 //主要递归方法打印长度为length的所有可能的字符串
 void print_str（const char str []，std :: string prefix，const int n，const int lenght）
 
 {
 
 if（lenght == 1）
 
 {
 $ b b for（int j = 0; j  
 {
 //我注释了这个ligne，所以如果你想使用你的数组打印你的排列，得到一个screnn与排列打印2次
 // std :: cout< prefix + str [j]< std :: endl; 
 permutations.push_back（prefix + str [j]）; //我们将用来存储排列在
}中的向量// b 
 $ b} //基本情况：lenght = 1，打印字符串lenght乘以+剩余字母
 
 else 
 
 {
 
 
 //逐个添加str中的所有字符，递归调用lenght等于lenght -1 
 for（int i = 0; i  
 //添加的输入的下一个字符
 print_str（str，prefix + str [i] ，n，lenght-1）; 
 //lenght减少，因为我们添加了一个新字符
 
} 
 NumberOfPermutations = permutations.size（）; 
} 
  
 
I would like to know if there is already an implementation in CPP to find all permutations of n characters of length k(1,2,3,4 etc) with repetitions. I hope there is but i could not find. 
For example if string= (A,B,C,D) and i want find all permutations of string with repetitions of length k =2.
The output will be something like :
AA
AB
AC
AD
.
.
.
DD
total permutations of 16.  
 解决方案 
Simple recursive solution which will work for you for sure.
Let me first re-write your specification: Print all permutations with repetition of characters
For a given string of size n, there will be n^k possible strings of length "length". The idea is to start from an empty output string (we call it prefix in following code). One by one add all characters to prefix. For every character added, print all possible strings with current prefix by recursively calling for "length" equals to "length"-1.
#include <string>
#include <iostream>


void print_str(const char*,std::string,const int, const int);

int main()

{

    int lenght = 2;

    char str[] = {'A', 'B', 'C', 'D'};



    int n = sizeof str;

    print_str(str, "", n, lenght);  //Note: this function works on all cases and not just the case above

    return 0;

}

// The main recursive method to print all possible strings of length "length"
    void print_str(const char str[],std::string prefix,const int n, const int lenght)

    {

        if (lenght == 1)

            {

                for (int j = 0; j < n; j++)

                std::cout << prefix + str[j] << std::endl;

            }//Base case: lenght = 1, print the string "lenght" times + the remaining letter

        else

            {


               // One by one add all characters from "str" and recursively call for "lenght" equals to "lenght"-1
                for (int i = 0; i < n; i++)

                // Next character of input added
                print_str(str, prefix + str[i], n, lenght - 1);
                // "lenght" is decreased, because we have added a new character

            }

    }
Here is the execution of the code above:
References:
http://www.geeksforgeeks.org/print-all-permutations-with-repetition-of-characters/
http://www.geeksforgeeks.org/print-all-combinations-of-given-length/
Update: this update is writen answring the following spec.
#include <string>
#include <iostream>
#include <vector>

void print_str(const char*,std::string,const int, const int);
std::vector<std::string> permutations ;  // the vector permutations which will hold all the permutations, 
                                       //if you want you can use it for later use or you can use the array below which is nothing than a copy of this vector.

int NumberOfPermutations = 0; // this variable holds the number of permutations 



int main()

{

    int lenght = 3;

    char str[] = {'A', 'B', 'C', 'D'};

    int n = sizeof str;
//here we loop through all the possible lenghts 1, 2 and 3
    for (int k = 1; k <= lenght; k++)

               {

                   print_str(str, "", n, k);  //Note: this function works on all cases and not just the case above
                }


    std::string* permut_array =  new std::string[NumberOfPermutations]; // the array that we will use to store the permutations in

    std::copy(permutations.begin(), permutations.end(), permut_array); // here we copy the vector into the array 

    //if you want you can use your array to print the permutation as folow

    for (int k = 0; k < NumberOfPermutations; k++)

               {

                   std::cout << permut_array[k] << std::endl;
                }

    return 0;

}

// The main recursive method to print all possible strings of length "length"
    void print_str(const char str[],std::string prefix,const int n, const int lenght)

    {

        if (lenght == 1)

            {

                for (int j = 0; j < n; j++)

               {
                   // i commented this ligne so that if you want to use your array to print your permutations you will not get a screnn with permutations printed 2 times
                   //std::cout << prefix + str[j] << std::endl; 
                   permutations.push_back(prefix + str[j]); // the vector that we will use to store the permutations in
                }

            }//Base case: lenght = 1, print the string "lenght" times + the remaining letter

        else

            {


               // One by one add all characters from "str" and recursively call for "lenght" equals to "lenght"-1
                for (int i = 0; i < n; i++)

                // Next character of input added
                 print_str(str, prefix + str[i], n, lenght - 1);
                // "lenght" is decreased, because we have added a new character

            }
        NumberOfPermutations = permutations.size();
    }
                        
这篇关于长度k从n个字符的所有排列，在CPP中重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！