如何用C ++中的替换创建排列？ [英] How to create permutations with replacement in C++?

问题描述

注意：在阅读templatetypedef的帖子后，看起来我想要计算一个集合的笛卡尔乘积与自身一定次数。

不完全确定我想要解决的问题是什么，但它似乎非常接近排列替换我。

基本上，我的问题是这个。
给定一个数组，例如：

  {1，2，3} 
  

和一个大小，例如2.
我需要输出：

  {1,1}，{1,2}，{1,3}，{2,1}，{2,2}，... 
  

如果size为3，那么它将是

  {1,1,1}，{1,1,2}，{1,1,3}，{1,2,1}，{1,2,2}，{1,2 ，3}，{1,3,1} ... 
  

/ p>



为了我的问题，我有一个15个数字的输入大小，所以我想我可以创建15个循环，但这似乎是一个黑客。 / p>



感谢。

编辑：我在编辑我的问题后不知道我在问什么，基本上是同样的问题。
在阅读templatetypedef的帖子后，似乎我想计算一个集合的笛卡尔乘积本身大小的次数。

解决方案

您尝试计算集合{1，2​​}的笛卡尔积 ，3}自己十五次。您可以使用简单的递归算法非常优雅地执行此操作：

• 要计算一个集合的笛卡尔乘积，包含原始集合的每个元素的单例列表。


• 计算自身n> 1次的集合的笛卡尔乘积：
  
  
  
  • 递归计算集合本身的笛卡尔乘积n-1次。
  
  
  • 对于输入列表的每个元素x：
    
    
    
    • 对于到目前为止产生的每个序列S：
      
      
      
      • 将序列S + x添加到输出集合。
      
      
    
    
  
  


• 返回输出集合。 b
  $ b

  在（稍微低效）C ++代码：

    vector< vector< int> CartesianPower（const vector< int& input，unsigned k）{
   if（k == 1）{
   vector< vector< int>结果; 
   for（int value：input）{
   result.push_back（{value}）; 
  } 
   return result; 
  } else {
   vector< vector< int>>结果; 
   vector< vector< int>> lowerPower = CartesianProduct（input，k  -  1）; 
   
   for（int elem：input）{
   for（vector< int> sublist：lowerPower）{
   sublist.push_back（elem）; 
   result.push_back（sublist）; 
  } 
  } 
   
  返回结果; 
  } 
  } 
    

  希望这有助于！

  
  

  Note:After reading templatetypedef's post, it seems like I'm trying to compute the cartesian product of a set with itself a certain amount of times.

  I am not completely sure what the problem I'm trying to solve is called, but it seems pretty close to permutation with replacement to me.

  So basically, my problem is this. Given an array, for example:

  {1, 2, 3}
  

  and a size, say 2. I need to output:

  {1,1},{1,2},{1,3},{2,1},{2,2},...
  

  If size was 3, then it would be

  {1,1,1},{1,1,2},{1,1,3},{1,2,1},{1,2,2},{1,2,3},{1,3,1}...
  

  How would I do this?

  For the purposes of my problem, I have an input size of 15 numbers, so I guess I could create 15 for loops, but that seems like a hack to me.

  Thanks.

  Edit: I edited my problem after becoming not sure what I was asking and what I actually needed were essentially the same problem. After reading templatetypedef's post, it seems like i'm trying to compute the cartesian product of a set with itself size amount of times.

  解决方案

  You are trying to compute the Cartesian product of the set {1, 2, 3} with itself fifteen times. You can do this very elegantly with a simple recursive algorithm:

  • To compute the Cartesian product of a set with itself just once, return a set containing singleton lists of each of the elements of the original set.
  • To compute the Cartesian product of a set with itself n > 1 times:
    • Recursively compute the Cartesian product of the set with itself n - 1 times.
    • For each element x of the input list:
      • For each sequence S produced so far:
        • Add the sequence S + x to the output set.
    • Return the output set.

  In (somewhat inefficient) C++ code:

  vector<vector<int>> CartesianPower(const vector<int>& input, unsigned k) {
      if (k == 1) {
          vector<vector<int>> result;
          for (int value: input) {
              result.push_back( {value} );
          }
          return result;
      } else {
          vector<vector<int>> result;
          vector<vector<int>> smallerPower = CartesianProduct(input, k - 1);
  
          for (int elem: input) {
              for (vector<int> sublist: smallerPower) {
                  sublist.push_back(elem);
                  result.push_back(sublist);
              }
          }
  
          return result;
       }
  }
  

  Hope this helps!

  这篇关于如何用C ++中的替换创建排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！