Algoritmus na vytvorenie kombinácií z dvojrozmerného poľa. – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

Peter910
Duch
16. 8. 2018   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 188.167.173.–
KIIV
~ Moderátor
+43
God of flame
17. 8. 2018   #2
-
0
-

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.

Nahlásit jako SPAM
IP: 89.24.57.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Peter910
Duch
17. 8. 2018   #3
-
0
-

#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.

Nahlásit jako SPAM
IP: 2a01:c846:27f:ed00:a868:b...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 4 hosté

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý