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 の数を選択し、4 のすべての組み合わせについて、5 つの数の組み合わせが (21 - A) になる数を調べます。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

ネストされた 6 つのループ (または再帰関数) が必要で、合計が 21 に達するとすぐにbreakループする必要があります。