整数解を列挙するアルゴリズムが知りたい

Question

前提・実現したいこと

はじめまして。
現在、下記の条件を満たす整数a[i]の組を列挙するコードを書きたいと思っています。
∑(i = 1からNまで) a[i] = K (N, Kは、N >= 1, K >= 0 を満たす整数)

具体的には、例えば
X + Y + Z = 6
を満たすような整数X,Y,Zの組を求めるような感じです。
組の数を求めるのではなく、各組を列挙したいです。

Nがわかっていれば、N-1回for文を入れ子にして列挙できそうですが、
Nが分からない場合、どのように一般化して書いたらいいか教えてもらいたいです。
よろしくお願いいたします。

Comments

[Zuishin]

N が 1 の時
6
N が 2 の時
0 6, 1 5, 2 4, 3 3, 4 2, 5 1, 6 0
N が 3 の時
0 0 6, 0 1 5, 0 2 4, 0 3 3, 0 4 2, 0 5 1, 0 6 0, 1 0 5, 1 1 4, 1 2 3, 1 3 2, 1 4 1, 1 5 0, 2 0 4, 2 1 3, 2 2 2, 2 3 1, 2 4 0, 3 0 3, 3 1 2, 3 2 1, 3 3 0, 4 0 2, 4 1 1, 4 2 0, 5 0 1, 5 1 0, 6 0 0

再帰でできそうですね。

[program_test]

コメントありがとうございます。
再帰でできるかと思って考えてはいたのですが、どうも漸化式が作れず。。
もう少し詳しく教えていただけますでしょうか。

[Zuishin]

i が 0 の時、K の取りうる範囲は 0 から 6 までです。
i が 1 の時、K の取りうる範囲は 0 から 6 - a[0] までです。
i が 2 の時、K の取りうる範囲は 0 から 6 - a[0] - a[1] までです。
取りうる範囲をすべて列挙するのを N 回繰り返してください。
動作確認済みのサンプルコードを回答に書きますが、C# 9.0 なので提出はできません。

Answer 1

#nullable enable

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

namespace ConsoleApp1
{
	class Program
	{
		static Func<TArg, TResult> Memoize<TArg, TResult>(Func<Func<TArg, TResult>, TArg, TResult> func)
			where TArg : notnull
		{
			var dic = new Dictionary<TArg, TResult>();

			TResult memoized(TArg arg)
			{
				if (!dic.TryGetValue(arg, out TResult result))
				{
					result = func(memoized, arg);
					dic[arg] = result;
				}
				return result;
			}

			return memoized;
		}

		static void Main()
		{
			var func = Memoize<(int, int), string[]>((memoized, args) =>
			{
				(int n, int sum) = args;

				return n switch
				{
					< 1 => throw new ArgumentOutOfRangeException(nameof(args)),
					1 => new[] { sum.ToString() },
					_ => Enumerable
							.Range(0, sum + 1)
							.SelectMany(a => memoized((n - 1, sum - a)).Select(b => $"{a} {b}"))
							.ToArray()
				};
			});

			while (true)
			{
				Console.Write("N = ");
				if (!int.TryParse(Console.ReadLine(), out int n)) break;

				Console.Write("Sum = ");
				if (!int.TryParse(Console.ReadLine(), out int sum)) break;

				foreach (var item in func((n, sum)))
				{
					Console.WriteLine(item);
				}
			}
		}
	}
}

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net5.0</TargetFramework>
  </PropertyGroup>

</Project>

Comments

[program_test]

コードまで書いていただきありがとうございます。
まだまだ自分の知らない記法があり、勉強しながら理解しようと思います。
ありがとうございました。