[ALG] Combineren van gegevens / sets *

[raptorix]

Ik zit met het volgende probleem, ik zoek een set die bestaat uit 12 kenmerken, laten we ze voor het gemak letters noemen.

Bijvoorbeeld: ADEFGHKMPUTZ

Nu zijn er koppeltjes die bestaan uit 2 letters, bijvoorbeeld:

AL
BN
KD
UG
etc,

Het aantal koppeltjes kan vrij groot zijn.
Doel is om zoveel mogelijk Sets te vormen die bestaan uit de koppeltjes van 2 letters.
Van de sets bestaan meerdere soorten, maar dat is niet heel belangrijk omdat dit eventueel met de hand gechecked kan worden.
Een set mag overigens maar 1 keer een koppeltje gebruiken.


Maar volgens mij bestaan hier ook slimme algoritmes voor, weet iemand misschien hoe dit probleem heet? Of anders wat zinnigs hierover kan roepen? De oplossing wordt uiteindelijk C# maar pseudo code voldoet natuurlijk prima.

[NMe]

Je hebt dus een grote set met 12 kenmerken en een boel kleine sets met 2 kenmerken, en je wil van de grote set zoveel mogelijk kleine maken? Ik begrijp eerlijk gezegd niet zoveel van je verhaal... Kun je een voorbeeld geven van de precieze uitvoer die je wenst bij een bepaalde invoer?

[bigbeng]

Dat heet permutaties.

Met een array een geneste for lus moet je al een aardig eind komen.

edit:
echt net op tijd voor != spuit11

[ Voor 21% gewijzigd door bigbeng op 05-06-2008 16:22 ]

[Janoz]

Het genereren van permutaties is basic for lusjes werk, maar wat is nu eigenlijk de bedoeling met die meerdere sets? Dat is me namelijk niet helemaal duidelijk.

[raptorix]

Ik zal het proberen uit te leggen, stel je zoekt een groepen van telkens 6 mensen, met ieder 2 unieke eigenschappen. Idee is dus dat het programma zoveel mogelijk van deze groepen kan samenstellen. Trouwens gegroet iedereen, was hier al tijdje niet meer geweest.

[raptorix]

Ik denk dat ik hier al heel eind mee kom: http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate

[Verwijderd]

raptorix schreef op donderdag 05 juni 2008 @ 16:27:
Ik denk dat ik hier al heel eind mee kom: http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate

Ik denk dat je hier meer aan hebt: Wikipedia: Permutatie. Stap twee is kijken hoe jouw probleem uitgewerkt zou moeten worden met die theorie. Stap drie is dan de boel implementeren. Ik zou er eerst voor zorgen dat ik de theorie begreep in plaats van wat losse C# code opzoeken.

[ Voor 12% gewijzigd door Verwijderd op 05-06-2008 17:30 ]

[pkuppens]

raptorix schreef op donderdag 05 juni 2008 @ 16:16:
... originele post ...

Eerst het probleem proberen duidelijk te krijgen.
Leg het eens heel precies uit voor 4 kenmerken. A,B,C, en D.

1. Zijn AB en BA verschillend?
2. Zijn AB,CD en CD,AB verschillend?
3. Moet een set van koppeltjes alle eigenschappen ABCD afdekken?
4. Is AB,AC,AD een oplossing? Want als koppeltjes zijn ze uniek.
5. Bestaan alle koppels wel, of worden vele koppels niet gevormd omdat ze niet als combinatie in een persoon zitten?

Als je het aantal mogelijkheden wilt tellen, dan hier effe Introductie tot Combinatoriek:
12 letters op willekeurige volgorde zetten kan op 12! = 12*11*10*..*3*2*1 manier.
Als 1 niet het geval is: er zitten dubbeltellingen in als AB = BA, nl. 2^6. Je eindoplossing dan delen door 2^6.
Als 2. niet het geval is, kun je de koppeltjes op 6! volgorden zetten die fundamenteel gelijk zijn, dan moet je je oplossing door 6! delen.
Bovenste sommetjes zijn allen geldig als 3. waar is.
4. hoop ik niet, want dat maakt het vast nog lastiger.
5. komen we wel uit.

[ Voor 6% gewijzigd door pkuppens op 05-06-2008 21:02 ]

[raptorix]

PKuppens: AB en BA zijn identiek, elk kenmerk kan als uniek worden gezien.
Zelfde geld voor casus 2
Voor 3: In Principe wel, er zijn uitzonderingen waarin aantal "wildcards" mogelijk zijn, maar dat heeft niet hoogste prio voor oplossen van probleem..
4) Nee, want aan dubbele kenmerken heb ik niets.
5) Alle koppels bestaan, echter het aantal "gunstige" koppels komt minder vaak voor en het aantal "ongunstige" koppels komt vaker voor.

Ik wil deze applicatie maken voor een spel waarbij iedereen 2 resources heeft. In het spel kan je 5 handelsbetrekkingen ondergaan met mensen met andere resources, op deze manier kan je dus een totaal van 12 resources bereiken. Er zijn een aantal gunstige combinaties, in principe zijn er 8 echt goede sets van resources. Met dit programma wil ik dus mensen aan elkaar koppelen.

[pkuppens]

raptorix schreef op vrijdag 06 juni 2008 @ 11:01:
PKuppens: AB en BA zijn identiek, elk kenmerk kan als uniek worden gezien.
Zelfde geld voor casus 2
Voor 3: In Principe wel, er zijn uitzonderingen waarin aantal "wildcards" mogelijk zijn, maar dat heeft niet hoogste prio voor oplossen van probleem..
4) Nee, want aan dubbele kenmerken heb ik niets.
5) Alle koppels bestaan, echter het aantal "gunstige" koppels komt minder vaak voor en het aantal "ongunstige" koppels komt vaker voor.

Ik wil deze applicatie maken voor een spel waarbij iedereen 2 resources heeft. In het spel kan je 5 handelsbetrekkingen ondergaan met mensen met andere resources, op deze manier kan je dus een totaal van 12 resources bereiken. Er zijn een aantal gunstige combinaties, in principe zijn er 8 echt goede sets van resources. Met dit programma wil ik dus mensen aan elkaar koppelen.

Zoals ik het nu begrijp, uit je antwoorden op 1..5 wil je alle sets van 6 koppels tellen, waarbij de volgorde in de koppels niet uitmaakt.
Problemen met het vaker laten voorkomen van bepaalde sets, of verbieden, omdat ze te gunstig zijn kun je dan later oplossen.

Als je recursie snapt zou ik het met recursie oplossen, dat is wat eleganter dan for loopjes.

code:

aanroep: genereer('abcdefghijkl'); // geeft de set koppels op alfabetische volgorde

functie set = genereer(string) =
   if (empty(string)) return {}; // problemen als lengte 1 is  :) , maar dat kon niet?
   a = head(string), // 'a'
   for (b in tail(string)), // achtereenvolgens 'b', 'c', 'd', ...
      koppel = a+b;
      rest = genereer(string zonder a en b);
      set = { koppel } U rest;
   end for;
   return set;
end function;

Wel nog wat puzzelen met data types, en hoe de union U als functie eruit ziet.

Waarom ik denk dat dit correct is? In een set koppels mag altijd 'a' vooraan staan,
en de rest is de elegantie van recursie.

[Verwijderd]

Ik volg het niet helemaal, maar het lijkt hierop:

Java:

    public static void main(String[] args) {
        char[] values = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t'};      
        for (int i = 0; i < (values.length - 1); ++i) {
            for (int j = (i + 1); j < values.length; ++j) {
                System.out.println(String.valueOf(values[i]) + String.valueOf(values[j]));
            }
        }
    }

[pkuppens]

Verwijderd schreef op vrijdag 06 juni 2008 @ 13:09:
Ik volg het niet helemaal, maar het lijkt hierop:

Java:

    public static void main(String[] args) {
        char[] values = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t'};      
        for (int i = 0; i < (values.length - 1); ++i) {
            for (int j = (i + 1); j < values.length; ++j) {
                System.out.println(String.valueOf(values[i]) + String.valueOf(values[j]));
            }
        }
    }

Dit geeft je alle koppeltjes ('ab' , 'ac', 'ad', .., 'st'), maar volgens mij zoekt TS sets van koppeltjes
{'ab', 'cd', 'ef'}, ... {'ac', 'bf', 'de'}, ... {'af', 'be', 'cd'} etc...

Het zijn er trouwens

code:

(12 !) / ((2^6) * (6 !)) = 10 395

[Met 6 maar 15 :)]

[raptorix]

Dank voor alle input, ik heb het werkend

code:

        public static String[] getCombinations(String[] sourceArray, int size)
        {
            int i, j;
            int sourceLength = sourceArray.Length;
            if (sourceLength < size) { size = sourceLength; }
            int[] indices = new int[size];
            int count = 1;
            for (i = 0; i < size; )
            {
                count *= (sourceLength - i);
                count /= ++i;
            }
            String[] items = new String[count];
            int indexCap = 1 + sourceLength - size;
            for (i = 0; i < count; ++i)
            {
                for (j = 0; j < size; ++j) { items[i] += sourceArray[j + indices[j]] + " "; }
                items[i] = items[i].Substring(0, items[i].Length - 1);

                while (0 < j)
                {
                    indices[--j]++;
                    if (indices[j] < indexCap) { break; }
                }
                if (indices[0] < indexCap)
                { for (j = 0; j < size; ++j) { if (indices[j] == indexCap) { indices[j] = indices[j - 1]; } } }
            }
            return items;
        }

Probleem was wel dat met veel items de array van return items ontzettend groot wordt. Ik knal er nu random 30 items in, en herhaal dat, niet zo zuiver, maar effectief genoeg

[sam.vimes]

Dit heet: de combinaties van 2 uit 12. Als de volgorde van de setjes er wel toe doet, is de naam: de permutaties van 2 uit 12. Het aantal combinaties van m uit n is te berekenen met n!/m!/(n-m)!, in dit geval 12!/2!/10! = 66. Uitgebreid artikel hier: Wikipedia: Combination