Combinaciones de listas CON repeticiones en Scala

Question

Intentando aprender un poco de Scala y encontré este problema. Encontré una solución para todas las combinaciones sin repeticiones here y entiendo un poco la idea detrás, pero parte de la sintaxis me está arruinando. Tampoco creo que la solución sea apropiada para un caso CON repeticiones. Me preguntaba si alguien podría sugerir un poco de código del que podría trabajar. Tengo un montón de material sobre combinatoria y entiendo el problema y las soluciones iterativas, solo estoy buscando la forma más simple de hacerlo.

Gracias

Answer 1

Entiendo su pregunta ahora. Creo que la forma más fácil de lograr lo que desea es hacer lo siguiente:

def mycomb[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
    case 0 => List(List()) 
    case _ => for(el <- l; 
       sl <- mycomb(n-1, l dropWhile { _ != el })) 
       yield el :: sl 
} 

def comb[T](n: Int, l: List[T]): List[List[T]] = mycomb(n, l.removeDuplicates) 

El método comb sólo llama mycomb con duplicados eliminados de la lista de entrada. Al eliminar los duplicados, es más fácil probar más tarde si dos elementos son "iguales".El único cambio que he hecho en su método mycomb es que cuando se llama al método recursivamente, quito los elementos que aparecen antes de el en la lista. Esto es para evitar que haya duplicados en la salida.

> 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)) 

Answer 2

La pregunta se reformuló en una de las respuestas - espero que la pregunta misma se editó también. Alguien más respondió la pregunta correcta. Dejaré ese código a continuación en caso de que alguien lo encuentre útil.

Esta solución es confuso como el infierno, de hecho. Una "combinación" sin repeticiones se llama permutación. Podría ir de esta manera:

def perm[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
    case 0 => List(List()) 
    case _ => for(el <- l; 
        sl <- perm(n-1, l filter (_ != el))) 
       yield el :: sl 
    } 

Si la lista de entrada no está garantizada para contener elementos únicos, como se sugiere en otra respuesta, que puede ser un poco más difícil. En lugar de filter, que elimina todos los elementos, necesitamos eliminar solo el primero.

def perm[T](n: Int, l: List[T]): List[List[T]] = { 
    def perm1[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
     case 0 => List(List()) 
     case _ => for(el <- l; 
        (hd, tl) = l span (_ != el); 
        sl <- perm(n-1, hd ::: tl.tail)) 
       yield el :: sl 
    } 
    perm1(n, l).removeDuplicates 
} 

Solo un poco de explicación. En el para, tomamos cada elemento de la lista, y regresamos listas compuestas de la misma, seguidas por la permutación de todos los elementos de la lista, excepto por el elemento seleccionado.

Por ejemplo, si tomamos la lista (1,2,3), vamos a componer las listas formadas por 1 y MMA (Lista (2,3)), 2 y Perm (Lista (1,3)) y 3 y permanente (Lista (1,2)).

Dado que estamos haciendo permutaciones de tamaño arbitrario, hacemos un seguimiento de cuánto tiempo puede ser cada subpermutation. Si una subpermutación es de tamaño 0, es importante que devolvamos una lista que contenga una lista vacía. ¡Note que esta no es una lista vacía! Si devolviéramos Nil en el caso 0, no habría ningún elemento para sl en la permanente de llamadas, y todo el "para" arrojaría Nil. De esta forma, a sl se le asignará Nil, y compilaremos una lista el :: Nil, produciendo List (el).

Estaba pensando en el problema original, sin embargo, y voy a publicar mi solución aquí por referencia. Si quería decir que no había elementos duplicados en la respuesta como resultado de elementos duplicados en la entrada, solo agregue un removeDuplicates como se muestra a continuación.

def comb[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 
} 

Es un poco feo, lo sé. Tengo que usar toList para convertir el rango (devuelto por "a") en una lista, de modo que "para" sí mismo devuelva una lista. Podría eliminar "l1", pero creo que esto deja más claro lo que estoy haciendo.Puesto que no hay filtro de aquí, modificándolo para eliminar duplicados es mucho más fácil:

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 
} 

Answer 3

Daniel - No estoy seguro de lo que Alex entiende por duplicados, puede ser que a continuación se ofrece una respuesta más apropiada:

def perm[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
    case 0 => List(List()) 
    case _ => for(el <- l.removeDuplicates; 
       sl <- perm(n-1, l.slice(0, l.findIndexOf {_ == el}) ++ l.slice(1 + l.findIndexOf {_ == el}, l.size))) 
      yield el :: sl 
} 

Ejecutar como

perm(2, List(1,2,2,2,1)) 

esto da:

List(List(2, 2), List(2, 1), List(1, 2), List(1, 1)) 

en contraposición a:

List(
    List(1, 2), List(1, 2), List(1, 2), List(2, 1), 
    List(2, 1), List(2, 1), List(2, 1), List(2, 1), 
    List(2, 1), List(1, 2), List(1, 2), List(1, 2) 
) 

La maldad dentro de la llamada permanente anidada es la eliminación de un solo 'el' de la lista, me imagino que hay una manera mejor de hacerlo, pero no puedo pensar en una .

Answer 4

me escribió una solución similar al problema en mi blog: http://gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-to.html

principio pensé de generar todas las posibles combinaciones y eliminar los duplicados, (o utilizar conjuntos, que se encarga de la propia duplicaciones), sino como el problema se especificó con listas y todas las combinaciones posibles serían demasiado, he encontrado una solución recursiva al problema:

para obtener las combinaciones de tamaño n, tomar un elemento del conjunto y anexarlo a todas las combinaciones de conjuntos de tamaño n-1 de los elementos restantes, unir las combinaciones de tamaño n de los elementos restantes. Eso es lo que hace el código

//P26 
def combinations[A](n:Int, xs:List[A]):List[List[A]]={ 
    def lift[A](xs:List[A]):List[List[A]]=xs.foldLeft(List[List[A]]())((ys,y)=>(List(y)::ys)) 

    (n,xs) match { 
     case (1,ys)=> lift(ys) 
     case (i,xs) if (i==xs.size) => xs::Nil 
     case (i,ys)=> combinations(i-1,ys.tail).map(zs=>ys.head::zs):::combinations(i,ys.tail) 
    } 
} 

cómo leerlo:

tuve que crear una función auxiliar que "levantar" una lista en una lista de listas

La lógica es en el partido instrucción:

Si desea todas las combinaciones del tamaño 1 de los elementos de la lista, simplemente cree una lista de listas en la que cada sublista contiene un elemento del original (esa es la función "levantar")

Si las combinaciones son la longitud total de la lista, sólo devuelve una lista en la que el único elemento es la lista de elementos (sólo hay una combinación posible!)

De lo contrario, toma la cabeza y la cola de la lista, calcule todas las combinaciones de tamaño n-1 de la cola (llamada recursiva) y anexe la cabeza a cada una de las listas resultantes (.map (ys.head :: zs)) concatene el resultado con todas las combinaciones de tamaño n de la cola de la lista (otra llamada recursiva)

¿Tiene sentido?

Answer 5

parte integral Mientras tanto, se han convertido en combinaciones de las colecciones Scala:

scala> val li = List (1, 1, 0, 0) 
li: List[Int] = List(1, 1, 0, 0) 

scala> li.combinations (2) .toList 
res210: List[List[Int]] = List(List(1, 1), List(1, 0), List(0, 0)) 

Como vemos, que no permite la repetición, sino permitir que ellos es sencillo con combinaciones sin embargo: Enumerar todos los elementos de su colección (0 a li.size-1) y mapa de elemento de la lista:

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)) 

Answer 6

Esta solución fue publicada el Código de Rosetta: http://rosettacode.org/wiki/Combinations_with_repetitions#Scala

def comb[A](as: List[A], k: Int): List[List[A]] = 
    (List.fill(k)(as)).flatten.combinations(k).toList 

Answer 7

Realmente no está claro lo que está pidiendo. Podría ser una de las pocas cosas diferentes. Primero serían combinaciones simples de diferentes elementos en una lista. Scala lo ofrece con el método combinations() de colecciones. Si los elementos son distintos, el comportamiento es exactamente el que espera de la definición clásica de "combinaciones". Para combinaciones de n elementos de elementos p, habrá p!/N! (P-n)! combinaciones en la salida.

Sin embargo, si hay elementos repetidos en la lista, Scala generará combinaciones con el elemento que aparece más de una vez en las combinaciones. Pero solo las diferentes combinaciones posibles, con el elemento posiblemente replicado tantas veces como existan en la entrada. Genera solo el conjunto de combinaciones posibles, por lo tanto, elementos repetidos, pero no combinaciones repetidas. No estoy seguro si subyacente hay un iterador a un Set real.

Ahora, lo que en realidad quiere decir si entiendo correctamente es combinaciones de un conjunto dado de diferentes elementos p, donde un elemento puede aparecer varias veces n veces en la combinación.

Bueno, volviendo un poco, para generar combinaciones cuando hay elementos repetidos en la entrada, y quiere ver las combinaciones repetidas en la salida, el camino a seguir es simplemente generarlo por "fuerza bruta" "usando n bucles anidados. Tenga en cuenta que realmente no hay nada de bruto, es solo el número natural de combinaciones, en realidad, que es O (p^n) para n pequeña, y no hay nada que pueda hacer al respecto. Sólo se debe tener cuidado para recoger estos valores correctamente, así:

val a = List(1,1,2,3,4) 
def comb = for (i <- 0 until a.size - 1; j <- i+1 until a.size) yield (a(i), a(j)) 

resultando en

scala> comb 
res55: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (1,3), (1,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)) 

Esto genera las combinaciones de estos valores repetidos en una, creando en primer lugar las combinaciones intermedias de 0 until a.size como (i, j) ...

Ahora para crear las "combinaciones con repeticiones" sólo hay que cambiar los índices de este tipo:

val a = List('A','B','C') 
def comb = for (i <- 0 until a.size; j <- i until a.size) yield (a(i), a(j)) 

producirá

List((A,A), (A,B), (A,C), (B,B), (B,C), (C,C)) 

Pero no estoy seguro de cuál es la mejor manera de generalizar esto a combinaciones más grandes.

Ahora cierro con lo que estaba buscando cuando encontré esta publicación: una función para generar las combinaciones de una entrada que contiene elementos repetidos, con índices intermedios generados por combinations(). Es bueno que este método produce una lista en lugar de una tupla, por lo que significa en realidad podemos resolver el problema con un "mapa de un mapa", algo que estoy seguro de que nadie más ha propuesto aquí, pero eso es bastante ingenioso y hará que tu amor por FP y Scala crezca un poco más después de que lo veas!

def comb[N](p:Seq[N], n:Int) = (0 until p.size).combinations(n) map { _ map p } 

resultados en

scala> val a = List('A','A','B','C') 
scala> comb(a, 2).toList 
res60: List[scala.collection.immutable.IndexedSeq[Int]] = List(Vector(1, 1), Vector(1, 2), Vector(1, 3), Vector(1, 2), Vector(1, 3), Vector(2, 3))