Liste des combinaisons avec des répétitions à Scala

La question a été reformulée dans l'une des réponses - j'espère que la question elle-même est également modifiée. Quelqu'un d'autre a répondu à la bonne question. Je laisserai ce code ci-dessous au cas où quelqu'un le trouve utile.

Cette solution est confuse comme l'enfer, en effet. Une "combinaison" sans répétition est appelée permutation. Cela pourrait aller comme ceci: p> xxx pré>

si la liste d'entrée n'est pas garantie de contenir des éléments uniques, comme suggéré dans une autre réponse, il peut être un peu plus difficile. Au lieu de filtrer, qui supprime tous les éléments, nous devons retirer uniquement le premier. P> xxx pré>

juste un peu d'explication. Dans la mesure, nous prenons chaque élément de la liste et les listes de retour sont composées de celle-ci suivie de la permutation de tous les éléments de la liste, à l'exception de l'élément sélectionné. P>

par exemple, si nous prenons la liste (1 , 2,3), nous composerons des listes formées par 1 et Perm (liste (2,3)), 2 et Perm (liste (1,3)) et 3 et perm (liste (1,2)).

Puisque nous faisons des permutations de taille arbitraire, nous gardons une trace de combien de temps chaque sous-performatrice peut être. Si une sous-performatrice est la taille 0, il est important de renvoyer une liste contenant une liste vide. Notez que ce n'est pas une liste vide! Si nous sommes retournés nul au cas échéant, il n'y aurait aucun élément pour SL dans la permanente appelante, et l'ensemble "pour" céderait nul. De cette façon, SL sera attribué nul, et nous composerons une liste EL :: NIL, Cording List (El). P>

Je pensais au problème initial, et je posterai mon solution ici pour référence. Si vous vouliez dire ne pas avoir des éléments dupliqués dans la réponse à la suite d'éléments dupliqués dans l'entrée, ajoutez simplement un retrait de retrait comme indiqué ci-dessous. P>

def comb[T](n: Int, l: List[T]): List[List[T]] = {
  def comb1[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for(i <- (0 to (l.size - n)).toList;
                    l1 = l.drop(i);
                    sl <- comb(n-1, l1.tail))
                yield l1.head :: sl
    }
  comb1(n, l).removeDuplicates
}

Daniel - Je ne sais pas ce que Alex signifiait par des duplicats, il se peut que ce qui suit fournit une réponse plus appropriée: xxx

exécuté comme xxx

Ceci donne: xxx

par opposition à: xxx

la nezsitude à l'intérieur de la permanente imbriquée Appel est en train de supprimer une seule "El" de la liste, j'imagine qu'il y a une meilleure façon de le faire, mais je ne peux pas penser à un.

J'ai écrit une solution similaire au problème de mon blog: http://gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-a.html

Je pensais d'abord générer toutes les combinaisons possibles et éliminer les doublons (ou les ensembles d'utilisation, qui s'occupe des duplications elles-mêmes), mais comme le problème a été spécifié avec des listes et toutes les combinaisons possibles seraient trop nombreuses, je suis venu Avec une solution récursive au problème:

Pour obtenir les combinaisons de la taille N, prenez un élément de l'ensemble et appendez-le à toutes les combinaisons des ensembles de taille N-1 des éléments restants, Union les combinaisons de la taille n des éléments restants. C'est ce que le code fait xxx

comment le lire:

J'ai dû créer une fonction auxiliaire qui "soulever" une liste dans une liste de listes

La logique est dans l'instruction de correspondance:

Si vous souhaitez toutes les combinaisons de la taille 1 des éléments de la liste, créez une liste de listes dans lesquelles chaque subliste contient un Elément de l'original (c'est la fonction "Ascenseur")

Si les combinaisons sont la longueur totale de la liste, renvoyez simplement une liste dans laquelle le seul élément est la liste des éléments (il n'y a qu'une combinaison possible !)

Sinon, prenez la tête et la queue de la liste, calculez toutes les combinaisons de la taille N-1 de la queue (appel récursif) et appendez la tête à chacune des listes résultantes (.map (ys.head :: zs)) concaténate le résultat avec toutes les combinaisons de la taille N de la queue de la liste (un autre appel récursif)

a un sens?

Je comprends votre question maintenant. Je pense que le moyen le plus simple de réaliser ce que vous voulez est de faire ce que vous voulez faire ce qui suit:

> comb(3, List(1,2,3))
> List[List[Int]] = List(
    List(1, 1, 1), List(1, 1, 2), List(1, 1, 3), List(1, 2, 2), 
    List(1, 2, 3), List(1, 3, 3), List(2, 2, 2), List(2, 2, 3), 
    List(2, 3, 3), List(3, 3, 3))

> comb(6, List(1,2,1,2,1,2,1,2,1,2))
> List[List[Int]] = List(
    List(1, 1, 1, 1, 1, 1), List(1, 1, 1, 1, 1, 2), List(1, 1, 1, 1, 2, 2), 
    List(1, 1, 1, 2, 2, 2), List(1, 1, 2, 2, 2, 2), List(1, 2, 2, 2, 2, 2), 
    List(2, 2, 2, 2, 2, 2))

Entre-temps, les combinaisons sont devenues une partie intégrante des collections Scala: xxx pré>

Comme on le voit, il ne permet pas de répéter, mais de leur permettre est simple avec des combinaisons: énumérer chaque élément de votre collection (0 à li.size-1) et de la carte de l'élément dans la liste: P>

scala> (0 to li.length-1).combinations (2).toList .map (v=>(li(v(0)), li(v(1))))
res214: List[(Int, Int)] = List((1,1), (1,0), (1,0), (1,0), (1,0), (0,0))

Cette solution a été postée sur Rosetta Code: http://roseettacode.org/wiki/comminations_with_repetitions#scala < / a> xxx