algorithm - 循环遍历所有配置

Question

我想不出一个好方法来做到这一点：

我想遍历加起来为 21 的 6 个数字的所有组合。这些数字必须大于 0 和整数。

例如：

 21 0 0 0 0 0 
 20 1 0 0 0 0 
 20 0 1 0 0 0 
 ...
 1 2 3 4 5 6
 etc...

你们能给我一个线索吗？

Answer 1

这个问题类似于 next_permutation 问题。https://github.com/zwxxx/LeetCode/blob/master/Next_Permutation.cpp。我们可以通过修改如何获取下一个元素来解决这个问题。以下是示例代码。

#include <iostream>

using namespace std;

bool findNext(int *perm)
{
    if (perm[5] == 21) 
        return false;
    int i;
    for(i = 0; i < 6; i++)
        if (perm[i] != 0)
            break;
    perm[i+1]++;
    perm[i]--;
    if (i > 0) {
        int tmp = perm[i];
        perm[i] = perm[0];
        perm[0] = tmp;                                                                                                                                                                                                                    
    }   
    return true;
}

void printPerm(int *perm)
{
    for (int i = 0; i < 6; i++) {
        cout << perm[i] << " ";
    }   
    cout << endl;
}

int main()
{
    int n[6];
    n[0] = 21; 
    for (int i =1; i < 6; i++)
        n[i] = 0;
    printPerm(n);
    while (findNext(n)) {
        printPerm(n);
    }   
    printPerm(n);

}

Answer 2

为第一个数字 A 选择一个数字，然后找出 5 个数字的组合有多少个组合加起来为 (21 - A) 等等，对于所有 4 的组合等等。1 个案例可以（最多）1 个组合。为了保持唯一性，您可以添加数字必须不增加的约束

所以它会是这样的：

findcombinations(sum, length, max) {

if(length == 1)
  return 1;
else {
   for(int i = 0; i <= sum && i <= max; i++)
       return findcombinations(sum - i; length -1; i)
}
}

Answer 3

我更喜欢下一个排列方法。或者您可以使用 6 个嵌套 for 循环的蛮力，这更易于实现。

这是从 ChengYi He 的帖子转换而来的 Next permutation 的 C# 版本

using System;
using System.Collections.Generic;
using System.Linq;

static class Extensions
{
    public static string GetString(this IEnumerable<int> arr)
    {
        return arr.Aggregate("", (a, b) => a + " " + b);
    }
}

class Program
{
    const int Sum = 21;
    const int Len = 6;

    static void Main(string[] args)
    {
        var result = new List<string>();
        Run(result);
        result.ForEach(Console.WriteLine);

        Console.WriteLine(string.Format("N: {0}\nPress a key to exit", 
            result.Count));
        Console.ReadKey();
    }

    static void Run(IList<string> result)
    {
        var n = new int[Len];
        n[0] = Sum;

        result.Add(n.GetString());
        while (FindNext(n))
        {
            result.Add(n.GetString());
        }
    }

    static bool FindNext(IList<int> perm)
    {
        if (perm.Last() == Sum)
        {
            return false;
        }

        int i;
        for (i = 0; i < Len; i++)
        {
            if (perm[i] != 0)
            {
                break;
            }
        }

        perm[i + 1]++;
        perm[i]--;
        if (i > 0)
        {
            int tmp = perm[i];
            perm[i] = perm[0];
            perm[0] = tmp;
        }
        return true;
    }
}

蛮力版本在 C# 中是这样的

static void Main(string[] args)
{
    var result = new List<string>();
    for (int a = 0; a <= Sum; a++)
        for (int b = 0; b <= Sum; b++)
            for (int c = 0; c <= Sum; c++)
                for (int d = 0; d <= Sum; d++)
                    for (int e = 0; e <= Sum; e++)
                        for (int f = 0; f <= Sum; f++)                            
                            if(a+b+c+d+e+f==Sum)                                
                                result.Add(string.Format(
                                    "{0} {1} {2} {3} {4} {5}",
                                        a,b,c,d,e,f));

    result.ForEach(Console.WriteLine);                            
    Console.WriteLine(string.Format("N: {0}\nPress a key to exit",
                                    result.Count));
    Console.ReadKey();
}

Answer 4

您将需要六个嵌套循环（或递归函数），并且一旦总和达到 21，您就应该break循环。