Listing combinazioni con ripetizioni a Scala

Question

Cercando di imparare un po 'di Scala e corse in questo problema. Ho trovato una soluzione per tutte le combinazioni senza repetions qui e ho un po 'di capire il idea dietro di esso, ma alcuni dei sintassi è mi rovinare. Anche io non credo che la soluzione è appropriato per un caso con ripetizioni. Mi chiedevo se qualcuno potrebbe suggerire un po 'di codice che ho potuto lavorare. Ho un sacco di materiale sul calcolo combinatorio e capire il problema e le soluzioni iterative ad esso, sto solo cercando il modo scala-y di farlo.

Grazie

Answer 1

ho capito la tua domanda ora. Penso che il modo più semplice per ottenere ciò che si desidera è di fare quanto segue:

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)

Il metodo comb chiama solo mycomb con i duplicati rimossi dalla lista di input. Rimuovendo i duplicati significa che è poi facile verificare successivamente se due elementi sono 'lo stesso'. L'unico cambiamento che ho fatto per il metodo di el è che quando il metodo viene chiamato in modo ricorsivo mi spogliano gli elementi che appaiono prima <=> nella lista. Questo è quello di smettere di essere lì duplicati in uscita.

> 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

Nel frattempo, le combinazioni sono diventati parte integrante delle collezioni 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))

Come si vede, non permette la ripetizione, ma per consentire loro è semplice con combinazioni però: Enumera ogni elemento della vostra collezione (da 0 a li.size-1) e mappare elemento della 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 3

ho scritto una soluzione simile al problema nel mio blog: http://gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-to.html

Per prima cosa ho pensato di generare tutte le combinazioni possibili e la rimozione dei duplicati, (o utilizzare i set, che si prende cura delle sé duplicazioni), ma come il problema è stato specificato con le liste e tutte le possibili combinazioni sarebbe troppo, I' ve si avvicinò con una soluzione ricorsiva al problema:

per ottenere le combinazioni di dimensione n, prendere un elemento dell'insieme e aggiungerlo a tutte le combinazioni di insiemi di dimensione n-1 degli elementi rimanenti, unione le combinazioni di dimensione n degli elementi rimanenti. Questo è ciò che fa il codice

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

Come per leggerla:

ho dovuto creare una funzione ausiliaria che "lift" una lista in una lista di liste

La logica è nella dichiarazione partita:

Se si desidera che tutte le combinazioni di dimensioni 1 degli elementi della lista, basta creare una lista di liste in cui ogni sottoelenco contiene un elemento di quella originale (che è la funzione di "lift")

Se le combinazioni sono la lunghezza totale della lista, appena Restituisce una lista in cui l'unico elemento è la lista degli elementi (c'è una sola combinazione possibile!)

In caso contrario, prendere la testa e la coda della lista, calcolare tutte le combinazioni di dimensione n-1 della coda (chiamata ricorsiva) e aggiungere il testa a ciascuno una delle liste risultanti (.map (ys.head :: zs)) concatenare il risultato con tutte le combinazioni di dimensione n della coda della lista (un'altra chiamata ricorsiva)

Ha senso?

Answer 4

La domanda è stata riformulata in una delle risposte - Spero che la domanda stessa viene modificato anche. Qualcun altro ha risposto alla domanda corretta. Lascio che il codice qui sotto nel caso in cui qualcuno trova utile.

Questa soluzione è fuorviante in quanto l'inferno, anzi. Una "combinazione" senza ripetizioni si chiama permutazione. Si potrebbe andare in questo modo:

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
  }

Se l'elenco di ingresso non è garantito per contenere gli elementi unici, come suggerito in un'altra risposta, può essere un po 'più difficile. Invece di filtro, che rimuove tutti gli elementi, abbiamo bisogno di rimuovere solo il primo.

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 po 'di spiegazione. Nel per, prendiamo ogni elemento della lista, e torniamo liste composte da essa seguita dalla permutazione di tutti gli elementi della lista, tranne per l'elemento selezionato.

Per esempio, se prendiamo List (1,2,3), ci comporre liste formate da 1 e Perm (Lista (2,3)), 2 e Perm (Lista (1,3)) e 3 e Perm (Lista (1,2)).

Dal momento che stiamo facendo permutazioni arbitrarie dimensioni, teniamo traccia di quanto tempo ogni subpermutation può essere. Se un subpermutation è formato 0, è importante che restituisce una lista contenente un elenco vuoto. Si noti che questa non è una lista vuota! Se siamo tornati Nil nel caso in cui 0, non ci sarebbe alcun elemento per sl nel perm chiamare, e il tutto "per" produrrebbe Nil. In questo modo, sl verrà assegnato Nil, e noi provvederemo a comporre una lista el :: Nil, cedendo Lista (el).

Stavo pensando al problema originale, però, e vi posterò la mia soluzione qui per riferimento. Se non significava avere elementi duplicati in risposta a causa di elementi duplicati in ingresso, basta aggiungere un removeDuplicates come illustrato di seguito.

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
}

E 'un po' brutto, lo so. Devo usare toList per convertire la gamma (restituito da "a") in un elenco, in modo che "per" sé sarebbe restituire un elenco. Ho potuto fare a meno "L1", ma penso che questo rende più chiaro quello che sto facendo. Poiché non v'è alcun filtro qui, modificandolo per rimuovere i duplicati è molto più semplice:

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 5

Daniel - non sono sicuro di quello che Alex intende con i duplicati, può essere che la segue fornisce una risposta più appropriata:

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
}

Esegui come

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

questo dà:

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

in contrapposizione 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 cattiveria all'interno della chiamata di perm nidificato sta rimuovendo una singola 'el' dalla lista, immagino ci sia un modo migliore per farlo, ma non riesco a pensare a una sola.

Answer 6

Questa soluzione è stato pubblicato il Codice 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

E 'davvero non è chiaro quello che stai chiedendo. Potrebbe essere una delle poche cose diverse. In primo luogo sarebbe semplici combinazioni di elementi diversi in una lista. Scala offre che con il metodo combinations() da collezioni. Se gli elementi sono distinti, il comportamento è esattamente quello che ci si aspetta dalla classica definizione di "combinazioni". Per le combinazioni di n elementi di elementi p ci sarà p! / N! (P-n)! combinazioni in uscita.

Se ci sono elementi nella lista ripetuto, però, Scala genererà combinazioni con la voce che appare più di una volta nelle combinazioni. Ma solo le diverse combinazioni possibili, con l'elemento eventualmente replicate quante volte come esistono in ingresso. Esso genera solo l'insieme di possibili combinazioni, così elementi ripetuti, ma combinazioni non utilizzate. Non sono sicuro se ad esso sottesa v'è un iteratore ad un vero e proprio Set.

Ora quello che in realtà dire se ho capito bene è combinazioni da un dato insieme di diversi elementi p, in cui un elemento può comparire più volte n volte nella combinazione.

Bene, tornando un po ', per generare combinazioni quando ci sono elementi ripetuti in entrata, e vuoi vedere le combinazioni ripetuti nell'output, il modo per andare a questo proposito è solo per generarlo da "forza bruta" usando i loop n annidati. Si noti che non c'è davvero nulla bruta a questo proposito, è solo il numero naturale di combinazioni, in realtà, che è O (p ^ n) per n piccolo, e non c'è niente che tu possa fare al riguardo. Hai solo dovrebbe essere attenti a scegliere questi valori correttamente, in questo modo:

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

con conseguente

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

Questo genera le combinazioni di questi valori ripetuti in una, mediante la creazione di combinazioni intermedie di 0 until a.size come (i, j) ...

Ora per creare le "combinazioni con ripetizioni" devi solo cambiare gli indici in questo modo:

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

produrrà

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

Ma non sono sicuro di quello che è il modo migliore per generalizzare questo a combinazioni più grandi.

Ora chiudere con quello che cercavo quando ho trovato questo post: una funzione per generare le combinazioni da un ingresso che contiene elementi ripetuti, con indici intermedi generati da <=>. E 'bello che questo metodo produce un elenco invece di una tupla, in modo che significa che possiamo davvero risolvere il problema applicando una "mappa di una mappa", qualcosa che io non sono sicuro che chiunque altro ha proposto qui, ma che è piuttosto carino e renderà il vostro amore per la FP e Scala crescere un po 'di più dopo lo vedi!

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

risultati in

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