Algorithmes de permutation en C#

Question

Je suis aux prises avec cet algorithme que j'ai besoin d'écrire. J'utilise C#. Dire que j'ai un List<Bag> et que j'ai un List<Lunch>. J'ai besoin d'écrire un algorithme qui énumérera toutes les permutations de déjeuners dans tous les sacs.

Par exemple, disons il y a 3 déjeuners et 2 sacs:

// Permutation 1 
Bag 1, Lunch 1 
Bag 2, Lunch 1 

// Permutation 2 
Bag 1, Lunch 1 
Bag 2, Lunch 2 

// Permutation 3 
Bag 1, Lunch 1 
Bag 2, Lunch 3 

// Permutation 4 
Bag 1, Lunch 2 
Bag 2, Lunch 1 

// Permutation 5 
Bag 1, Lunch 2 
Bag 2, Lunch 2 

// Permutation 6 
Bag 1, Lunch 2 
Bag 2, Lunch 3 

// Permutation 7 
Bag 1, Lunch 3 
Bag 2, Lunch 1 

// Permutation 8 
Bag 1, Lunch 3 
Bag 2, Lunch 2 

// Permutation 9 
Bag 1, Lunch 3 
Bag 2, Lunch 3 

Les deux permutations Bag 1 Lunch 1 and Bag 2 Lunch 2 et Bag 1 Lunch 2 and Bag 2 Lunch 1 sont différents parce que les sacs ont des capacités différentes, d'où ils doivent tous deux être énumérés.

Le nombre de sacs et déjeuners peut être n'importe quel nombre.

J'ai créé une classe appelée BagLunch qui contient une paire de sac et de lunch. La liste d'exemples que j'ai donnée ci-dessus serait stockée dans un List<BagLunch>.

Merci.

Answer 1

Alors vous voulez passer k sur n (k = sacs, n = déjeuners) tout en gardant la commande? J'espère que vous pouvez supposer que k < = n, sinon vous allez être coincé avec des sacs vides ...

Je ne veux pas gâcher vos devoirs entièrement, donc je vais vous diriger dans le droit direction. Cela demande une récursivité. Choisissez d'abord le déjeuner pour le premier sac, puis choisissez les déjeuners pour les sacs k-1 qui restent. Quand il ne vous reste plus qu'un sac, choisissez chacun des déjeuners restants jusqu'à ce que vous ayez fini.

EDIT:

Oh, un déjeuner peut résider dans deux sacs à la fois. Donc c'est n^k. Le plus court chemin serait d'utiliser la jointure LINQ suggérée ci-dessus, mais cela ressemble un peu à de la triche. Au lieu de cela, créez simplement un tableau d'entiers de K éléments, remplissez-le avec des zéros et commencez à en ajouter un à l'élément le plus à droite. Quand vous arrivez à N, remettez-le à zéro et portez-le à l'élément suivant. Vous comptez juste les nombres de K-chiffres dans la base-N. Après chaque itération, vous pouvez sortir l'assignation du sac.

Answer 2

Si vous autorisez des dupes [un déjeuner peut être dans deux sacs] - comme l'exemple suggère que vous avez #bags^#lunches possibilités.

Chaque sac a son propre "choix" unique que le déjeuner à mettre
Pour générer ces possibilités - juste "choisir" un déjeuner pour un sac, et invoquer récursivement l'algorithme. répétez pour chaque repas.

pseudo-code pour les générer:

generateAll(bags,lunches,sol): 
    if (bags is empty): 
     print sol 
     return 
    bag <- bags.first 
    bags.remove(bag) 
    for each lunch in lunches: 
    sol.append(BagLunch(bag,lunch) 
    generateAll(bags,lunches,sol) 
    sol.removeLast() 

Answer 3

Utilisez une croix se joindre à LINQ:

var qry = from bag in bags 
      from lunch in lunches 
      select new BagLunch 
      { Bag=bag, Lunch=lunch}; 
var baglunches = qry.ToList(); 

Edit:
Vous souhaitez modifier la clause select pour gérer la structure de votre classe BagLunch.

Answer 4

J'ai une méthode qui recrée votre exemple ci-dessus. L'approche est en fait de penser aux sacs comme des positions d'un nombre ... car si vous regardez votre exemple, vous pouvez le lire comme 11, 12,13,21,22,23. Ensuite, il s'agit de convertir en base Lunch.Count.J'ai aussi volé une méthode d'ici: https://stackoverflow.com/a/95331/483179 pour la convertir en n'importe quelle base dont il a été mentionné qu'elle n'a pas été testée, donc vous devrez peut-être construire quelque chose de plus robuste. Finalement, je n'ai fait aucun test de condition de bord, donc l'alimentation dans des sacs de 0 pourrait avoir des résultats inattendus. Voici ce que j'ai trouvé.

class Program 
{ 
    static List<Bag> bags = new List<Bag>(); 
    static List<Lunch> lunches = new List<Lunch>(); 

    static void Main(string[] args) 
    { 
     lunches.Add(new Lunch() { Num = 1 }); 
     lunches.Add(new Lunch() { Num = 2 }); 
     lunches.Add(new Lunch() { Num = 3 }); 
     bags.Add(new Bag() { Num = 1 }); 
     bags.Add(new Bag() { Num = 2 }); 

     int count = 0; 
     while (count < Math.Pow(lunches.Count, bags.Count)) 
     { 
      Console.WriteLine("Permutation " + count); 
      string countNumber = ConvertToBase(count, lunches.Count).PadLeft(bags.Count,'0'); 
      for (int x = 0; x < bags.Count; x++) 
      { 
       Console.WriteLine(bags[x] + " " + lunches[Convert.ToInt32((""+countNumber[x]))]); 

      } 
      Console.WriteLine(""); 
      count++; 
     } 
     Console.ReadLine(); 

    } 

    static string ConvertToBase(int value, int toBase) 
    { 
     if (toBase < 2 || toBase > 36) throw new ArgumentException("toBase"); 
     if (value < 0) throw new ArgumentException("value"); 

     if (value == 0) return "0"; //0 would skip while loop 

     string AlphaCodes = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 

     string retVal = ""; 

     while (value > 0) 
     { 
      retVal = AlphaCodes[value % toBase] + retVal; 
      value /= toBase; 
     } 

     return retVal; 
    } 

} 

class Lunch 
{ 
    public int Num { get;set;} 
    public override string ToString() 
    { 
     return "Lunch " + Num; 
    } 

} 
class Bag 
{ 
    public int Num { get;set;} 

    public override string ToString() 
    { 
     return "Bag " + Num; 
    } 
} 

et la sortie résultante:

Permutation 0 
Bag 1 Lunch 1 
Bag 2 Lunch 1 

Permutation 1 
Bag 1 Lunch 1 
Bag 2 Lunch 2 

Permutation 2 
Bag 1 Lunch 1 
Bag 2 Lunch 3 

Permutation 3 
Bag 1 Lunch 2 
Bag 2 Lunch 1 

Permutation 4 
Bag 1 Lunch 2 
Bag 2 Lunch 2 

Permutation 5 
Bag 1 Lunch 2 
Bag 2 Lunch 3 

Permutation 6 
Bag 1 Lunch 3 
Bag 2 Lunch 1 

Permutation 7 
Bag 1 Lunch 3 
Bag 2 Lunch 2 

Permutation 8 
Bag 1 Lunch 3 
Bag 2 Lunch 3