[ALG] 2D array mogelijkheden

[Verwijderd]

Ik heb al een tijd door dit forum gezocht maar kan het antwoord op mijn vraag niet vinden.

In mijn programma ontstaat een 2D array waarvan niet ieder element evenveel subelementen heeft. Het ziet er bijvoorbeeld als volgt uit:

JavaScript:

Possibilities = [ ["2", "3", "4"],
["5"],
["1"],
["4", "6"],
["8", "1"],
["1", "5"],
["1", "M2"]];

Nu wil ik hieruit een array van strings genereren van alle mogelijke combinaties (uit iedere array 1 element) zonder dat een combinatie dubbel voorkomt. Volgens mij denk ik te moeilijk maar ik heb geen idee hoe ik dit voor elkaar krijg.

[.oisyn]

Zoek eens op permutaties. 't Is doodsimpel, en in feite hetzelfde als je telt. Als je 3 cijfers hebt, dan ga je van 000 naar 009, dan wordt het middelste cijfer met 1 verhoogd en gaat de laatste weer op 0, dus 010, etc.

Hier gaat het precies hetzelfde, alleen tel je niet steeds tot 10 maar tot het aantal subelementen dat je per element hebt.

[Big Womly]

In een graaf steken en die overlopen

code:

  S
 /|\
2 3 4
 \|/
  5
  |
  1
 / \
4   6
|\ /|
| X |
|/ \|
8   1
|\ /|
| X |
|/ \|
1   5
|\ /|
| X |
|/ \|
1   M2
 \ /
  E

En deze via diepte eerst- of breedte eerst doorlopen

[ Voor 6% gewijzigd door Big Womly op 19-05-2010 12:40 ]

[Verwijderd]

Ik denk dat dit het beste werkt met een recursieve functie, waarbij iedere recursie een element uit je array doorloopt.

code:

P = Possibilities;

function bla(level, str){
  for(x=0; x<P[level].length; x++){
    if (level == P.length - 1) printf(str+P[level][x]+"\n");
    else{
      str += P[level][x] + ", ";
      bla(level+1, str);
    }
  }
}

bla(0, "");

Zoiets, vast behoorlijk buggy, ongetest enzo

[ Voor 57% gewijzigd door Verwijderd op 19-05-2010 12:47 ]

[Verwijderd]

Thanks guys! Ik ga hier even mee aan de slag

[RayNbow]

In een functionele taal is dit probleem redelijk eenvoudig. Benodigde boilerplate:
 

Haskell:

data [a]      -- list of values of type `a`
   = []       --   is either empty []
   | (a:[a])  --   or consists of a value of type `a`
              --   and a tail of type `[a]`


fmap f []        =  []                -- map  (functor)
fmap f (x:xs)    =  f x : fmap f xs

return a         =  [a]               -- unit (monad)

join xs          =  concat xs         -- join (monad)
concat []        =  []
concat (x:xs)    =  xs ++ concat xs

f >>= xs         =  join (fmap f xs)  -- bind (monad)


sequence []      =  return []
sequence (x:xs)  =  do v  <- x
                       vs <- sequence xs
                       return (v:vs)


{-
-- desugaring do-syntax gives:
sequence []      =  return []
sequence (x:xs)  =  x >>= (\v ->
                              sequence xs >>= (\vs ->
                                                   return (v:vs)
                                              )
                          )
-}

(Deze functionaliteit krijg je gratis met de Haskell prelude)

Een file met het probleem:

Haskell: Possibilities.hs

possibilities
 = [
    ["2", "3", "4"], 
    ["5"],
    ["1"],
    ["4", "6"],
    ["8", "1"],
    ["1", "5"],
    ["1", "M2"]
   ]

printList xs = mapM_ print xs

ghci> :l Possibilities.hs
[1 of 1] Compiling Main             ( Possibilities.hs, interpreted )
Ok, modules loaded: Main.
ghci> printList (sequence possibilities)

["2","5","1","4","8","1","1"]
["2","5","1","4","8","1","M2"]
["2","5","1","4","8","5","1"]
["2","5","1","4","8","5","M2"]
["2","5","1","4","1","1","1"]
["2","5","1","4","1","1","M2"]
["2","5","1","4","1","5","1"]
["2","5","1","4","1","5","M2"]
["2","5","1","6","8","1","1"]
["2","5","1","6","8","1","M2"]
["2","5","1","6","8","5","1"]
["2","5","1","6","8","5","M2"]
["2","5","1","6","1","1","1"]
["2","5","1","6","1","1","M2"]
["2","5","1","6","1","5","1"]
["2","5","1","6","1","5","M2"]
["3","5","1","4","8","1","1"]
["3","5","1","4","8","1","M2"]
["3","5","1","4","8","5","1"]
["3","5","1","4","8","5","M2"]
["3","5","1","4","1","1","1"]
["3","5","1","4","1","1","M2"]
["3","5","1","4","1","5","1"]
["3","5","1","4","1","5","M2"]
["3","5","1","6","8","1","1"]
["3","5","1","6","8","1","M2"]
["3","5","1","6","8","5","1"]
["3","5","1","6","8","5","M2"]
["3","5","1","6","1","1","1"]
["3","5","1","6","1","1","M2"]
["3","5","1","6","1","5","1"]
["3","5","1","6","1","5","M2"]
["4","5","1","4","8","1","1"]
["4","5","1","4","8","1","M2"]
["4","5","1","4","8","5","1"]
["4","5","1","4","8","5","M2"]
["4","5","1","4","1","1","1"]
["4","5","1","4","1","1","M2"]
["4","5","1","4","1","5","1"]
["4","5","1","4","1","5","M2"]
["4","5","1","6","8","1","1"]
["4","5","1","6","8","1","M2"]
["4","5","1","6","8","5","1"]
["4","5","1","6","8","5","M2"]
["4","5","1","6","1","1","1"]
["4","5","1","6","1","1","M2"]
["4","5","1","6","1","5","1"]
["4","5","1","6","1","5","M2"]

Of in C#:
 

C#:

static void Main(string[] args)
{
    var possibilities = new string[][] {
        new string[] {"2", "3", "4"}, 
        new string[] {"5"},
        new string[] {"1"},
        new string[] {"4", "6"},
        new string[] {"8", "1"},
        new string[] {"1", "5"},
        new string[] {"1", "M2"}
    };

    printListOfLists(Sequence(possibilities));
    Console.ReadKey();
}


static IEnumerable<IEnumerable<T>> Sequence<T>(IEnumerable<IEnumerable<T>> xs)
{
    if (!xs.Any())
    {
        return new List<IEnumerable<T>> { new List<T>{} };
    }
    else
    {
        var y = xs.First();
        var ys = xs.Skip(1);

        return from v in y
               from vs in Sequence(ys)
               select new List<T> { v }.Concat(vs);
    }
}


static void printListOfLists<T>(IEnumerable<IEnumerable<T>> xss)
{
    var s = String.Join("\n", 
                xss.Select(xs =>
                    "[" + String.Join(", ", xs.Select(x => x.ToString()).ToArray()) + "]"
                ).ToArray()
            );
    Console.WriteLine(s);
}

De bovenstaande code is alleen misschien niet helemaal precies wat je wilt. Hoe moet bijv. [["fo","f"], ["oo","o"]] worden afgehandeld? De code die ik getypt heb produceert iets als:

ghci> sequence [["fo","f"], ["oo", "o"]]
[["fo","oo"], ["fo","o"], ["f","oo"], ["f","o"]]

Als je dit gebruikt om strings te genereren, krijg je "fooo" en "fo" 1x, maar "foo" krijg je 2x.


Edit: Nu ook een JavaScript-variant:

JavaScript:

Array.prototype.flatten = function() {
    var res = [];
    for ( var i = 0; i < this.length; i++ )
        for ( var j = 0; j < this[i].length; j++ )
            res.push(this[i][j]);
    return res;
}

Array.prototype.flatMap = function(f) { return this.map(f).flatten() }

Array.prototype.sequence = function() {
    if (this.length == 0) {
        return [[]];
    }
    else {
        var x = this[0];
        var xs = this.slice(1);
        return x.flatMap(function(v) {
                             return xs.sequence().flatMap(
                                 function(vs) {
                                     return [[v].concat(vs)];
                                 }
                             );
                         });
    }
}


Possibilities = [ ["2", "3", "4"], 
["5"], 
["1"], 
["4", "6"], 
["8", "1"], 
["1", "5"], 
["1", "M2"]];

var seqs = Possibilities.sequence();
for (var i = 0; i < seqs.length; i++)
    print(seqs[i]);

Edit2:
Daadwerkelijk genereren van strings zonder dubbelen in Haskell:

Haskell:

foldr ((nub .) . liftM2 (++)) (return []) possibilities

[ Voor 11% gewijzigd door RayNbow op 19-05-2010 23:00 ]