Algoritmus na vytvorenie kombinácií z dvojrozmerného poľa. – Java – Fórum – Programujte.com

Ahojte, 

Potreboval by som pomôcť s vytvorením algoritmu na generovanie všetkých kombinácií z dvojrozmerného poľa.

Mám takúto štruktúru dvojrozmerného poľa objektu "groupItem" 

groupItem[][] itemss = {
    {
            new groupItem().setGroup(1).setItem(1),
            new groupItem().setGroup(1).setItem(2),
            new groupItem().setGroup(1).setItem(3),
            new groupItem().setGroup(1).setItem(4)
    },{
            new groupItem().setGroup(2).setItem(1),
            new groupItem().setGroup(2).setItem(2),
            new groupItem().setGroup(2).setItem(3),
            new groupItem().setGroup(2).setItem(4)
    },{
            new groupItem().setGroup(3).setItem(1),
            new groupItem().setGroup(3).setItem(2),
            new groupItem().setGroup(3).setItem(3),
            new groupItem().setGroup(3).setItem(4)
    }};

Potreboval by som pomoc s algoritmom na vytvorenie kombinácií kde nebudú duplicitne položky v kombinácií ale zároveň vždy bude aspoň jedna položka z každej, Tj v tomto prípade tu sú 4 položky od 1 po 4.

Pre urýchlenie generovania taktiež možnosť zadať koľko skupín môže byť maximálne v kombinácii, napríklad 2.

Príklad výstupu:  (Vysvetlenie: group -> 1:2 <- item)

[1:1, 1:2, 1:3, 1:4]
[1:1, 1:2, 1:3, 2:4]
[1:1, 1:2, 1:3, 3:4]
[1:1, 1:2, 1:3, 4:4]
[1:1, 1:2, 2:3, 1:4]
[1:1, 1:2, 2:3, 2:4]
[1:1, 1:2, 2:3, 3:4] // toto je už neplatne nakoľko sú tam 3 skupiny

Každý groupItem má ešte sumu, z ktorej budem hľadať najnižšiu súčet, ale to už nie je problém spraviť.

Moje aktuálne riešenie funguje, akurát je pomalé a pre maticu s 5 skupinami a 60 položkami je nefunkčné, nakoľko dojde pamäť. ( 60^5 kombinácii )

private List<List<groupItem>> combine(groupItem[][] matrix) {
    long sizeArray[] = new long[matrix.length];
    int counterArray[] = new int[matrix.length];
    int total = 1;
    for (int i = 0; i < matrix.length; ++i) {
        sizeArray[i] = matrix[i].length;
        if(total * matrix[i].length == 0)
            break;
        total *= matrix[i].length;
    }

    List<List<groupItem>> items = new ArrayList<>(total);
    for (int count = total; count > 0; --count) {
        List<groupItem> sum = new ArrayList<>();
        for (int i = 0; i < matrix.length; ++i) {
            sum.add(matrix[i][counterArray[i]]);
        }
        items.add(sum);
        for (int incIndex = matrix.length - 1; incIndex >= 0; --incIndex) {
            if (counterArray[incIndex] + 1 < sizeArray[incIndex]) {
                ++counterArray[incIndex];
                break;
            }
            counterArray[incIndex] = 0;
        }
    }
    return items;
}

Ďakujem za každú radu a pomoc.

Ja bych se byt tebou vykaslal na ukladani do listu a rovnou to zpracovaval.

Proste udelat iterator, ktery vrati aktualni radek. Tim bys vyresil pametovou narocnost i cas potrebny na vytvareni listu.

Pokud nezvladnes iterator, tak tomu predej treba "handler", kterymu predhodis kazdy radek.

#2 KIIV 

V tom groupItem je este aj suma ale nechcel som prekombinovat svoju otazku.

Toto je riesenie ktore mam v tomtom cykle "for (int count = total; count > 0; --count)"

MatrixSum sum = new MatrixSum(); // je ten povodny List<groupItem>
boolean priceIsNull = false;
for (int i = 0; i < matrix.length; ++i) {
    MatrixItem temp = matrix[i][counterArray[i]];
    sum.getItems().put(temp.getItemId(), temp);
    if (temp.getPrice() == null)
        priceIsNull = true;
}
if (!priceIsNull || withNull) {
    sum.count(); // spocita sucet cien danej kombinacie
    if(items.size() <= combinationNo) // ak je menej poloziek ako hladanych tak vlozim. vacsinou je hladanych 1 najmenej poloziek
        items.add(sum);
    else { // alebo nahradim polozku s najvyssiu cenu s touto.
        if(items.stream().anyMatch(i -> i.getSum().compareTo(sum.getSum()) > 0 )) {
            sortMatrixList();
            items.remove(items.size() - 1);
            items.add(sum);
        }
    }
}

Tj. v tom items je vzdy "int combinationNo" poloziek co je vacsinou 1-5.