Комбинаторика и вложенными для петель

Question

Предположим, что у меня есть ниже массив:

val x = Array(Array(1,2,3),Array(4,5,6),Array(7,8,9)) 

и хотят получить все комбинации, как так:

(1,4,7) (1,4,8) (1,4,9) (1,5,7) (1,5,8) (1,5,9) (1,6,7) ... (3,6, 7) (3,6,8) (3,6,9)

Я хотел бы написать:

def comb = for (
     a <- 0 until 3; 
     b <- 0 until 3; 
     c <- 0 until 3 
    ) yield (x(0)(a),x(1)(b),x(2)(c)) 
    comb foreach println 

Я хочу знать более эффективный способ сделать это, используя меньше памяти, что мне нужно сделать это для 10x16 массива, а не для 3x3.

Я попытался сделать 16 вложенных циклов, но у меня закончилась память, поскольку (я считаю) она должна сделать 10^16 комбинаций.

Answer 1

Для массива 10x16 у вас будет 10^16 комбинаций в памяти в качестве выхода. Единственное, что вы можете сделать здесь - получить его ленивым, используя итераторы вместо списков:

def comb = for (
    a <- 0 until 3 toIterator; 
    b <- 0 until 3 toIterator; 
    c <- 0 until 3 toIterator 
) yield (x(0)(a),x(1)(b),x(2)(c)) 

После этого вы можете отобразить + уменьшить результаты перед выводом.

Вы также можете посмотреть потоки, но они сохраняют результаты в памяти во время итерации - так что вам придется сводить их перед применением любых побочных эффектов (например, foreach).