Как привести все комбинации в порядок

Question

Например

Input

2,1,3

Output

1,1,1
1,1,2
1,1,3
2,1,1
2,1,2
2,1,3

Answer 1

Если я правильно понимаю вопрос, тогда это должно сработать (код на Haskell, выдаст результаты в порядке, отличном от примера)

combinations [] = []
combinations [x]
    |x > 0 = [x]:combinations [(x-1)]
    |otherwise = []
combinations (x:xs)
    |x > 0 = (map (\c -> x:c) (combinations xs)) ++ combinations((x-1):xs)
    |otherwise = []

Или это, чтобы получить его в том же порядке, что иВы дали (также просто более хорошее решение)

 combinations' [x] = [[c]|c<-[1..x]]
 combinations' (x:xs) = [c:d|c<-[1..x],d<-combinations' xs]

Мне понадобится немного времени, чтобы получить ответ на «императивном» языке (C, Java и т. д.).Это та вещь, где функциональные языки сияют.

---

Хорошо, так на Java.
Отказ от ответственности: этот код более или менее просто прямой перевод Haskell.Это не чистый или лучший способ сделать что-то.Я не проверял или действительно думал об этом, чтобы убедиться, что это правильно

public List<List<Integer>> combinations(List<Integer> workwith){
    List<List<Integer>> d = new LinkedList<LinkedList<Integer>>();
    if(workwith.size() == 1){
            int max = workwith.get(0);
        for(int i = 1; i=<max;i++){
            List<Integer> toAdd = new LinkedList<Integer>();
            toAdd.add(i);
            d.add(toAdd);
        }
        return d
    }
    Integer max = workwith.remove(0);
    List<List<Integer>> back = combinations(workwith);
    for(int i = 1, i<=max;i++)
        for(List<Integer> b: back){
        List<Integer> toAdd = new LinkedList<Integer>();
            toAdd.add(i);
            toAdd.addAll(b);
            d.add(toAdd)
        }
    }
    return d;
}

Answer 2

Не самый эффективный способ сделать это, но вот реализация C:

/* Assumes output is allocated with enough room for 'len' ints. */
/* Generates the 'num'-th combination in 'output'. */
void get_comb_number(int num, int len, int *input, int *output) {
    int i;
    for (i=num-i-1; i >= 0; --i) {
        output[i] = (num % input[i]) + 1;
        num /= input[i];
    }
}

Затем вы можете просто выполнить цикл от 0 до произведения ввода (для приведенного выше примера это будет 2*1*3 = 6), вызывая get_comb_number для каждой и распечатывая каждую комбинацию. Код немного неэффективен, потому что он должен вызывать функцию для каждой комбинации и выполнять все моды и деления для каждой комбинации, но IMO простота кода компенсирует это, если вам не нужна эффективность. Обратите внимание, что номер комбинации будет несколько быстрее переполнен, но при условии 32-битного целого числа вы потратите несколько минут на генерацию всех комбинаций в этой точке и намного дольше, пытаясь напечатать их все.

Answer 3

a [] - это входной вектор

int prod = 1;
for (int i = 0; i < a.size(); i++) prod *= a[i];  // find the count of lines in output

for (int i = 0; i < prod; i++){
     vector<int> b;                         // vector of the current output
     for (int j = a.size()-1; j >= 0; j--){ // for each output calculate its values
          b[j] = i % a[j];                  // each value will be between 0 and a[j]  
          i /= a[j];
     }
     for (int j = 0; j < a.size(); j++)     // output it
          cout << b[j] + 1 << " ";
     cout << endl;
}