Генерация комбинации элементов 2d списков в Groovy

Question

У меня есть двухмерный список, в котором количество строк составляет от 1 до 5, а количество элементов в каждой строке является динамическим.Давайте предположим, что у меня есть список типа

values = [[1,2,3], [4,5],[6,7,8,9]];

result = [[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,5,6],[2,5,7],[2,5,8],[2,5,9],[3,4,6],[3,4,7],[3,4,8],[3,4,9],[3,5,6],[3,5,7],[3,5,8],[3,5,9]]

, значения являются моим вводом, и мне нужен вывод в формате результата.

Я попытался реализовать функцию рекурсивным способом, но не смог,Моя функция

import groovy.transform.Field

List lines = [];
def function(row, col, lines)
{       
    if(row >= values.size())
    {           
        log.info("This should go inside result: " + lines);
        return;     
    }
    if(col >= values[row].size())
    {           
        return;         
    }   

    lines << values[row][col];  
    function(row+1,col,lines);
    lines.pop();
    function(row,col+1,lines);  
    return;
}


@Field
List values = [[1,2,3],[4,5],[6,7,8,9]];

@Field
List lst = [];


for(int i=0; i<values[0].size(); i++)
    function(0, i, lines)

Answer 1

class Some {

    static main(args) {

        def values = [[1,2,3], [4,5],[6,7,8,9]];

        int[] index = new int[values.size()];
        index.eachWithIndex { v, i ->
            index[i] = 0
        }
        print "["
        recursive(index, values);
        print "]"
    }


    public static recursive(int[] index, def values){
        print "["
        (0..(index.length - 1) ).each { i -> 
            print values[i][index[i]] + ( i == index.length - 1 ? "" : ",") 
        }
        print "]"


        boolean allVisited = false;
        for(int i = index.length - 1; i >= 0; i--  ){
            if (index[i] < values[i].size() - 1){
                index[i]++;
                for(int j = i + 1; j < index.length; j++  ){
                        index[j] = 0;
                    }
                break;
            }else if (i == 0){
                allVisited = true;
                break;
            }
        }

        if (!allVisited){
            print ", "
            recursive(index, values);
        }
    }

}

Вот рекурсивный алгоритм.Надеюсь, это поможет.

Answer 2

Groovy имеет встроенную функцию сбора combinations(), которая генерирует все возможные комбинации из списка списков элементов.

Пример использования:

assert [['a', 'b'],[1, 2, 3]].combinations() == [['a', 1], ['b', 1], ['a', 2], ['b', 2], ['a', 3], ['b', 3]]

Вы можете просто вызвать этот метод на values из исходного сценария:

def values = [[1,2,3], [4,5],[6,7,8,9]]

def expected = [[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,5,6],[2,5,7],[2,5,8],[2,5,9],[3,4,6],[3,4,7],[3,4,8],[3,4,9],[3,5,6],[3,5,7],[3,5,8],[3,5,9]]

def result = values.combinations()

assert ((expected as Set) == (result as Set))

---

Однако, если вы действительно хотите реализовать этот алгоритм самостоятельно, вы можетереализовать довольно простой хвостовой рекурсивный алгоритм, подобный показанному ниже:

import groovy.transform.CompileStatic
import groovy.transform.TailRecursive

@TailRecursive
@CompileStatic
<T> List<List<T>> combinations(final List<List<T>> xss, final List<List<T>> result = [[]]) {
    return !xss ? result : combinations(xss.tail(), process(xss.head(), result))
}

@CompileStatic
<T> List<List<T>> process(final List<T> xs, final List<List<T>> result) {
    return result.inject([]) { yss, ys -> yss + xs.collect { x -> ys + x } }
}

def values = [[1,2,3], [4,5],[6,7,8,9]]

def expected = [[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,5,6],[2,5,7],[2,5,8],[2,5,9],[3,4,6],[3,4,7],[3,4,8],[3,4,9],[3,5,6],[3,5,7],[3,5,8],[3,5,9]]

assert combinations(values) == expected