Как решить этот странный сценарий с несколькими циклами (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 букв (AL), а также размер "бита" не просто 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 = 1 шт. Макс.)

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';
            }
        }
    }
}

Answer 2

Черновой набросок в псевдо C # / Java:

Отображение A-L на индексы 0-11

const int[] maxvalues = { define max values for each var }
int[] counters = { initialize with 0s }

while (true)
{
  for(i in 11..0)
  {
    counters[i]++;
    if (counters[i] < maxvalues[i])
      break;   // for
    counters[i] = 0;
  }

  if (counters[0] == maxvalues[0])
    break;     // while

  print(counters.ToDisplayString());
}

(только что заметил, что вторая последовательность не совпадает с первой последовательностью в OP. Если OP верна, я думаю, я не "получил" последовательность)

Answer 3

Последовательность чисел, которую вы описали, можно перечислить, посчитав от 0 в базовом представлении чисел на единицу больше, чем количество «букв», используемых для создания ваших индивидуальных последовательностей.

Один простой способДля этого нужно использовать радикальный преобразователь из базы 10, который будет воздействовать на переменную, увеличиваемую за один цикл от 0 до максимального количества комбинаций, которые вы хотите получить.

Вот реализация:

void Main()
{
    for(int i=0; i< 50; i++){
     Console.Write(convert(5,i));
     Console.Write("\n");
    }
}

string convert(int N, int M){
    Stack<int> stack = new Stack<int>();

    while (M >= N){
     stack.Push(M %N);
     M = M / N;
    }
    string str = M.ToString();
    while(stack.Count() > 0)
      str = str + stack.Pop().ToString();
    return str;
}

Начальный вывод:

0 1 2 3 4 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 4041 42 43 44 100 101 102 103 104