[JAVA] Zoeken naar combinaties in 4 arrays

[codex]

Ik ben bezig met een klein project om mijn werk te vereenvoudigen. Uit een viertal array's moet ik combinaties zoeken die opgeteld een bepaalde hoeveelheid vertegenwoordigen. De arrays bestaan uit elk 10 getallen(double) en de ervaring leert dat er slechts 1 mogelijke 1 tot 4 delige combinatie bestaat, het kan dus zowel slechts postitie 5 uit array 1 zijn als 3 uit 1, 2 uit 3 en 7 uit 4. Per array gaat het om cumulatief gelijk oplopende getallen, positie 0 is bijvoorbeeld 4.56, positie 1 9.12 etc. Vanavond heb ik een poging gedaan door met een while loop op basis van de remainder te zoeken per array, maar hierin maakte ik een denkfout waardoor het niet functioneert. Is er iemand die een idee heeft hoe hiermee om te gaan?

[pedorus]

Deze vraag doet mij sterk hieraan denken:

quote: http://xkcd.com/287/

Je zou wellicht met een voorbeeld kunnen uitwerken wat je precies wil of code kunnen tonen van wat je hebt geprobeerd en wat er niet aan werkt..

[HMS]

Klinkt inderdaad als een Knapsack problem. Zie ook: Wikipedia: Knapsack problem

[KopjeThee]

Ik vraag me af wat er mis ging met je oplossing. Kan je de (relevante delen van) de code eens neerzetten? En uitleggen waar het mis gaat?

Kan je ook aangeven hoe groot die 4 arrays zijn? Bij vrij kleine arrays kun je dit natuurlijk vrij eenvoudig oplossen. Bij grotere kom je al vlug in de problemen, zie ook bovenstaande referenties.

[Daos]

Je kan toch gewoon 4 geneste for-loops pakken en bv bij -1 beginnen (bij -1 pak je dan niets uit het betreffende array)?

[Caelorum]

KopjeThee schreef op maandag 23 december 2013 @ 07:08:
[...] Kan je ook aangeven hoe groot die 4 arrays zijn? Bij vrij kleine arrays kun je dit natuurlijk vrij eenvoudig oplossen. Bij grotere kom je al vlug in de problemen, zie ook bovenstaande referenties.

reemprive schreef op maandag 23 december 2013 @ 00:53:
[...] De arrays bestaan uit elk 10 getallen(double) [...]

4 van 10 dus. Kleine arrays.

[pedorus]

Als het gaat om 0 of 1 item(s) uit iedere array pakken van 10 elementen, dan zijn er met 4 arrays slechts 11^4=14641 mogelijke combinaties. Dat is wel overzichtelijk natuurlijk, maar dan snap ik het programmeerprobleem niet zo.. Desnoods maak je de arrays eentje langer en voeg je een 0 op het begin toe, dan heb je vier simpele geneste forloopjes. Ik kan me voorstellen dat dat nog sneller is in java ook vanwege bounds checking.

[Daos]

Niets te doen vandaag

We hebben 4 for-loops als Method1. Een iteratieve manier met een grote while-loop als Method2 en natuurlijk nog recursief als Method3. De complexiteit is bij allen hetzelfde: O(N^4). (edit: bij recursief kan de complexiteit wel eens slechter zijn door het maken van een nieuwe lijst met indices; edit2: dat is geen factor N (aantal elementen per array), maar een constante factor (aantal arrays); het blijft dus O(N^4))

Aanroepen gaat zo:

C#:

int neededSum = 10;

int[] arrI = { 1, 2, 3 };
int[] arrJ = { 1, 3, 5 };
int[] arrK = { 2, 4, 6 };
int[] arrL = { 2, 3, 4 };

int[][] arr = new int[][] { arrI, arrJ, arrK, arrL };

Console.WriteLine("Method 1");
Method1(arrI, arrJ, arrK, arrL, neededSum);
Console.WriteLine();

Console.WriteLine("Method 2");
Method2(arr, neededSum);
Console.WriteLine();

Console.WriteLine("Method 3");
Method3(arr, neededSum);
Console.WriteLine();

Hulp-functie die in alle Methodes gebruikt wordt:

C#:

private static void PrintSum(int[][] arr, int[] indices, int sum)
{
    for (int i = 0; i < indices.Length; i++)
    {
        int index = indices[i];
        int value = index < 0 ? 0 : arr[i][index];

        Console.Write("{0}[{1}]={2}", (char)(i + 'I'), index, value);
        Console.Write(i < arr.Length - 1 ? " + " : " = ");
    }
    Console.WriteLine(sum);
}

Method1 (4 for-loops):

C#:

private static void Method1(int[] arrI, int[] arrJ, int[] arrK, int[] arrL, int neededSum)
{
    for (int i = -1; i < arrI.Length; i++)
    {
        int valueI = i < 0 ? 0 : arrI[i];
        for (int j = -1; j < arrJ.Length; j++)
        {
            int valueJ = j < 0 ? 0 : arrJ[j];
            for (int k = -1; k < arrK.Length; k++)
            {
                int valueK = k < 0 ? 0 : arrK[k];
                for (int l = -1; l < arrL.Length; l++)
                {
                    int valueL = l < 0 ? 0 : arrL[l];

                    int sum = valueI + valueJ + valueK + valueL;

                    if (sum == neededSum)
                        PrintSum(new int[][] { arrI, arrJ, arrK, arrL }, new int[] { i, j, k, l }, sum);
                }
            }
        }
    }
}

Method2 (iteratief met grote while-loop):

C#:

private static void Method2(int[][] arr, int neededSum)
{
    int[] indices = Enumerable.Repeat(-1, arr.Length).ToArray();

    bool increase = false;
    while (!increase)
    {
        int sum = arr.Select((a, i) => i).Sum(i => indices[i] < 0 ? 0 : arr[i][indices[i]]);

        if (sum == neededSum)
            PrintSum(arr, indices, sum);

        increase = true;
        for (int idx = indices.Length - 1; increase && idx >= 0; idx--)
            increase = (indices[idx] = (indices[idx] + 2) % (arr[idx].Length + 1) - 1) == -1;
    }
}

Method3 (recursief):

C#:

private static void Method3(int[][] arr, int neededSum)
{
    List<Tuple<int, int[]>> sums = GetSums(arr);
    sums = sums.Where(s => s.Item1 == neededSum).ToList();

    foreach (Tuple<int, int[]> sum in sums)
        PrintSum(arr, sum.Item2, sum.Item1);
}

private static List<Tuple<int, int[]>> GetSums(int[][] arr, int index = 0)
{
    List<Tuple<int, int[]>> current = new List<Tuple<int, int[]>>();
    current.Add(new Tuple<int, int[]>(0, new int[] { -1 }));
    current.AddRange(arr[index].Select((v, i) => new Tuple<int, int[]>(v, new int[] { i })));

    if (index == arr.Length - 1)
        return current;

    List<Tuple<int, int[]>> innerSums = GetSums(arr, index + 1);

    List<Tuple<int, int[]>> result = new List<Tuple<int, int[]>>();
    foreach (Tuple<int, int[]> item in current)
    {
        foreach (Tuple<int, int[]> innerSum in innerSums)
        {
            int sum = item.Item1 + innerSum.Item1;
            int[] indices = item.Item2.Concat(innerSum.Item2).ToArray();

            result.Add(new Tuple<int, int[]>(sum, indices));
        }
    }
    return result;
}

Sorry voor de lange lappen code. De hoeveelheid valt ook mij een beetje tegen. Iemand ideeen hoe het simpeler kan?

Volgens mij kan de complexiteit nog naar O(N^3) door neededSum - {de som tot dan toe} te zoeken in de laatste array. Met een hashmap kan dat zoeken in O(1). Dat is misschien iets voor later vandaag...

[ Voor 31% gewijzigd door Daos op 23-12-2013 19:43 . Reden: code ingekort ]

[Hydra]

Welke van die 3 is volgens jou het meest leesbaar? Medunkt dat je dan op optie 1 uitkomt.

Je houdt nu nog geen rekening in die methode dat je met een loop kunt stoppen als het totaal X is omdat de getallen oplopend zijn. Daar zit nog een winstpuntje.

[ Voor 47% gewijzigd door Hydra op 23-12-2013 16:08 ]

[Daos]

Het bedenken en programmeren was gewoon leuk. Velen zullen dat wel herkennen

Methodes 2 & 3 werken ook bij een ander aantal array's ipv van 4. Methode 2 valt wat betreft moeilijkheid nog wel mee. De while-loop bestaat uit 3 delen: 1. de som uitrekenen; 2. iets printen als de som is wat je zocht en 3. de indices ophogen.

Method 3 valt mij tegen. Recursief wordt het meestal simpeler, maar in dit geval niet echt. Het is wel een recursie volgens het boekje: De base-case geeft het laatste array terug (in een wat andere vorm) als je daar bent aangekomen. Daarna komt de recursieve aanroep. Het resultaat hiervan wordt gecombineerd met het huidige array en wordt vervolgens terug gegeven.

edit: verbeterde versie gemaakt; zie 2 posts hierboven

[ Voor 77% gewijzigd door Daos op 23-12-2013 19:08 . Reden: code verwijderd ]

[KopjeThee]

Caelorum schreef op maandag 23 december 2013 @ 12:01:
[...]

[...]

4 van 10 dus. Kleine arrays.

Ah, helemaal overheen gelezen. Er is dus geen enkel probleem
Maar ik kan me wel voorstellen dat je geen zin heb dit regelmatig handmatig te doen.

[Soultaker]

@Daos: je mist de pseudo-polynomiale oplossing die handig is voor knapsack-achtige problemen met kleine elementen.

Overigens heeft de TS het er over dat het verschil tussen elementen in elke array constant is (als ik z'n post tenminste correct interpreteer) dus dan wordt het meer een lineair probleem (hoewel de brute-force methode dan nog steeds kan werken, natuurlijk).

[Daos]

Soultaker schreef op maandag 23 december 2013 @ 20:02:
@Daos: je mist de pseudo-polynomiale oplossing die handig is voor knapsack-achtige problemen met kleine elementen.

Ik zie zo snel niet hoe je dit probleem daar naartoe kan converteren. Laat maar eens zien

[Soultaker]

Python:

neededSum = 10
arrays = [
  [ 1,2,3 ],
  [ 1,3,5 ],
  [ 2,4,6 ],
  [ 2,3,4 ] ]

can_make = [ True ] + [ None ]*neededSum
for i,array in enumerate(arrays):
  for x in range(neededSum, 0, -1):
    if not can_make[x]:
      for j,value in enumerate(array):
        if x >= value and can_make[x - value]:
          can_make[x] = (i,j)
          break

if can_make[neededSum]:
    x = neededSum
    while x > 0:
      i,j = can_make[x]
      print("Take %d (array %d, element %d)"%(arrays[i][j], i, j))
      x -= arrays[i][j]
else:
    print("Can't make %d!"%neededSum)

De tijdcomplexiteit is maximaal neededSum vermenigvuldigd met het totaal aantal elementen in de invoer-arrays. (Als je vier arrays hebt met maximaal N elementen dus O(N × neededSum).) Dat kan voordelig uitpakken ten opzichte van de O(N⁴) oplossing als de arrays langer worden (i.e. als neededSum < N³.)

[ Voor 8% gewijzigd door Soultaker op 23-12-2013 20:39 ]

[Sebazzz]

Maar gebruik alsjeblieft geen l of 1 of I voor de loop variable (i is wel goed).