c# - 如何解决这个奇怪的多循环场景(Java 或 C#)？

Question

我遇到了这个 - 可能是微不足道的 - 类似于二进制组合的循环/组合问题。我不知道如何有效地处理它。考虑这种情况，我需要一个独特的循环来按顺序传递所有这些组合:

Round  ABC

01.    000 <- values of A=0, B=0, C=0
02.    001
03.    010
04.    011
05.    100
06.    101
07.    110
08.    111

09.    002
10.    012
11.    102
12.    112
13.    020
14.    021
15.    120
16.    121 <- values of A=1, B=2, C=1
17.    022
18.    122
19.    220
20.    221
21.    222

除了有 12 个字母 (A-L)，而且“位”大小不仅仅是 0,1 或 2，而是任何整数(从 0 到 1000 或 1024，不要让它变得疯狂)。我知道这是一个巨大的组合负载，但我只会放弃也满足我其他条件的前几个。所以无需担心计算疯狂。

免责声明:订单必须完全如上所示。不是多个 FOR 循环，首先是 0-1024 用于 C，然后是 B。

提前致谢，我似乎找不到“算法”的方法。

更新:为 ABC/012 的组合添加了整个序列

问候，凯特

解释:

我在尝试解决分析硬币/纸币组合的金额问题时遇到了这个问题:

例如 $5001 找出 x 个最佳组合。

10x $500 + 1x $1
50x $100 + 1x $1
..

现在，字母 (A,B,C..) 对应于纸币或硬币的多种可能面值($1、$5、.. $100)。而基础对应于该纸币/硬币的数量(例如 $5001/$5000 = 1piece max.)

Answer 1

如果我猜对了你的序列，你会更容易递归地生成它

这里是 Java 中的一种方法，它应该生成一个与您的场景相匹配的序列。希望对您有所帮助(也许我稍后会添加更多解释):

public static void init() {
    // define constants
    final int length = 3;
    final char maxValue = '3';

    // define buffer
    final char[] array = new char[length]; java.util.Arrays.fill(array, '0');
    final boolean[] alreadySet = new boolean[length]; java.util.Arrays.fill(alreadySet, false);

    // fill first digit, then let the recursion take place
    for(char c = '1'; c <= (char)(maxValue); c++) {
        // iterate from lowest to highest digit
        for(int i = array.length-1; i >= 0; i--) {
            // set value
            array[i] = c;
            alreadySet[i] = true;
            // print value
            System.out.println(new String(array));
            // call recursion
            recursive(array, c, i, alreadySet, length);
            // unset value
            alreadySet[i] = false;
            array[i] = '0';
        }
    }
}

public static void recursive(char[] array, char lastValue, int lastIndex, boolean[] alreadySet, int leftToSet) {
    // if we didn't set all digits
    if(leftToSet > 0) {
        // iterate from lowest to highest digit
        for(int i = array.length-1; i >= 0; i--) {
            // missing all digits already set
            if(!alreadySet[i]) {
                // count from 1 to lastValue-1
                for(char c = '1'; c < lastValue; c++) {
                    // set value
                    array[i] = c;
                    alreadySet[i] = true;
                    // print value
                    System.out.println(new String(array));
                    // call recursion
                    recursive(array, c, i, alreadySet, leftToSet-1);
                    // unset value
                    alreadySet[i] = false;
                    array[i] = '0';
                }
            }
        }

        char c = lastValue;
        // iterate from lowest to highest digit
        for(int i = array.length-1; i > lastIndex; i--) {
            // missing all digits already set
            if(!alreadySet[i]) {
                // set value
                array[i] = c;
                alreadySet[i] = true;
                // print value
                System.out.println(new String(array));
                // call recursion
                recursive(array, c, i, alreadySet, leftToSet-1);
                // unset value
                alreadySet[i] = false;
                array[i] = '0';
            }
        }
    }
}