C ++中的分区和组合(组合)实现 [英] Partition and Composition (combinatorics) implementation in C++

问题描述

给定一个大小为M和N的矩阵，我们要在每一行中填充整数值(> = 0)，以便求和成一定值.

Given a matrix of size M and N, we want to fill in each row with integer value (>=0) so that it sums up to certain value.

请注意，M和N的尺寸是使用某些公式预先计算的，因此可以确保在给定所需条件(即以下sum_val)的情况下匹配填充.

Note that the dimension of M and N are pre-computed using certain formula, so that it is guaranteed to match the fill given the desired condition (i.e. sum_val below).

这是在R中的分区库下实现的.

This is implemented in R under Partition library.

library(partitions)

# In this example, we impose condition 
# that each rows must sum up to 2 in total
# And each row has 5 columns
sum_val <- 2
n <- 5
#The above two parameters are predefined.

t(as.matrix(compositions(sum_val, n)))
      [,1] [,2] [,3] [,4] [,5]
 [1,]    2    0    0    0    0
 [2,]    1    1    0    0    0
 [3,]    0    2    0    0    0
 [4,]    1    0    1    0    0
 [5,]    0    1    1    0    0
 [6,]    0    0    2    0    0
 [7,]    1    0    0    1    0
 [8,]    0    1    0    1    0
 [9,]    0    0    1    1    0
[10,]    0    0    0    2    0
[11,]    1    0    0    0    1
[12,]    0    1    0    0    1
[13,]    0    0    1    0    1
[14,]    0    0    0    1    1
[15,]    0    0    0    0    2

C ++中是否有任何现有的实现?

Is there any existing implementation in C++?

推荐答案

递归版本

这是一个递归解决方案.您有一个序列a，您可以在其中跟踪已经设置的数字.在递归调用列表中其余部分的函数之前，每次递归调用都会在循环中为这些元素之一分配有效数字.

Recursive version

Here is a recursive solution. You have a sequence a where you keep track of the numbers you already have set. Each recursive call will assign valid numbers to one of these elements in a loop, before recursively calling that function for the remainder of the list.

void recurse(std::vector<int>& a, int pos, int remaining) {
  if (remaining == 0) { print(a); return; }
  if (pos == a.size()) { return; }
  for (int i = remaining; i >= 0; --i) {
    a[pos] = i;
    recurse(a, pos + 1, remaining - i);
  }
}

void print_partitions(int sum_val, int n) {
  std::vector<int> a(n);
  recurse(a, 0, sum_val);
}

可以在 http://ideone.com/oJNvmu 上看到概念证明.

Proof of concept run visible at http://ideone.com/oJNvmu.

您在下面的评论表示性能问题.虽然I/O似乎很可能会消耗大部分性能，但这是一种迭代解决方案，它避免了递归方法的函数调用开销.

Your comment below indicates a performance problem. While it seems very likely that I/O is eating most of your performance, here is an iterative solution which avoids the function call overhead of the recursive approach.

void print_partitions(int sum_val, int n) {
  int pos = 0, last = n - 1;
  int a[n]; // dynamic stack-allocated arrays are a gcc extension
  for (int i = 1; i != n; ++i)
    a[i] = 0;
  a[0] = sum_val;
  while (true) {
    for (int i = 0; i != last; ++i)
        printf("%3d ", a[i]);
    printf("%3d\n", a[last]);
    if (pos != last) {
      --a[pos];
      ++pos;
      a[pos] = 1;
    }
    else {
      if (a[last] == sum_val)
        return;
      for (--pos; a[pos] == 0; --pos);
      --a[pos];
      int tmp = 1 + a[last];
      ++pos;
      a[last] = 0;
      a[pos] = tmp;
    }
  }
}

总体思想和打印内容的顺序与递归方法相同.无需维护计数器remaining，所有标记(或您正在分区的任何标记)都将立即放置在它们所属的位置，以便打印下一个分区. pos始终是最后一个非零字段.如果不是最后一个分区，则可以通过从pos获取一个令牌并将其移至此之后的位置来获取下一个分区.如果是最后一个，则从该最后一个位置取出所有令牌，找到之前的最后一个非零位置，并从该位置也取出一个令牌，然后将所有这些令牌转储到获得单个令牌的那个位置之后的位置.令牌.

The general idea and the order in which things are printed is the same as for the recursive approach. Instead of maintaining a counter remaining, all the tokens (or whatever it is you are partitioning) are immediately dropped in the place where they belong for the next partition to be printed. pos is always the last non-zero field. If that is not the last, then you obtain the next partition by taking one token from pos and moving it to the place after that. If it is the last, then you take all tokens from that last place, find the last non-zero place before that and take one token from there as well, then dump all these tokens onto the place after the one where you took the single token.

演示在 http://ideone.com/N3lSbQ 上运行.

这篇关于C ++中的分区和组合(组合)实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！