c# - いくつかの条件を満たすすべての集合 (ベクトル) を見つける

Question

この問題の解決策を探しています。セットの長さ (n)、セットの合計、およびセット内の要素になり得る最大値 k があります。

たとえば、n=5、k=3、合計=10

コードは、これらのセット [3, 3, 2, 1, 1] の一部を返す必要があります。[3, 2, 2, 2, 1]

これらのセットをc、c#で実用的に見つける方法は?

Answer 1

これは、Javaでの私の答えからの解決策です:

public class Main {

/**
 * @param args the command line arguments
 */
private static void printVectors(int[] p, int n) {

    for (int i = 0; i < n; i++) {
        System.out.print(p[i] + " ");
    }
    System.out.println();
}
//main function
private static void computeVectors(int[] n, int sum, int k, int k1, int i) {


    if (sum == 0) {

        printVectors(n, n.length);
    } else if (i < n.length) {

        for (int j = k; j >= 0; j--) {

            if (j <= k1) {
                n[i] = j;
                computeVectors(n, sum - j, sum - j, k1, i + 1);
            }
        }
    }
}
public static void main(String[] args) {
    // TODO code application logic here
    computeVectors(new int[5], 10, 3, 3, 0);

}

}

n=5 の場合、プログラムの出力の一部。合計=10; k=3 は:

3 1 2 2 2

3 1 2 1 3

3 1 1 3 2

3 1 1 2 3

3 1 0 3 3

3 0 3 3 1

3 0 3 2 2

3 0 3 1 3

3 0 2 3 2

3 0 2 2 3

3 0 1 3 3

2 3 3 2 0

2 3 3 1 1

2 3 3 0 2

2 3 2 3 0

ご覧のとおり、computeVectors は再帰関数です。問題は、この関数を再帰なしで実装できるかどうかです。以下のコードを試してみましたが、機能しません。

private static void computeVectorsNoRecursion(int[] n, int sum, int k, int i) {
    if (sum == 0) {

        printVectors(n, n.length);
    } else if (i < n.length) {
        int j=k;
       // for (int j = k; j >= 0; j--) {

            while (j <= k) {
                if(j>=0)
                {
                n[i]=j;
                i++;
              int temp=sum;
                sum=temp-j;
                k=temp-j;
                j--;
                if(i>=n.length)
                {
                    i=0;
                    printVectors(n, n.length);
                }

            }
        }

      //  }
    }
}