10

少しScalaを学ぼうとすると、この問題に遭遇しました。ここで繰り返しのないすべての組み合わせの解決策を見つけました。その背後にある考え方はある程度理解していますが、構文の一部が混乱しています。また、ソリューションが繰り返しのあるケースには適していないと思います。誰かが私が作業できるコードを少し提案できるかどうか疑問に思っていました. 私は組み合わせ論に関する資料をたくさん持っており、問題とそれに対する反復的な解決策を理解しています。それを行うためのスケーラな方法を探しているだけです。

ありがとう

4

7 に答える 7

8

私は今あなたの質問を理解しています。あなたが望むものを達成する最も簡単な方法は、次のことだと思います：

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)

このメソッドは、入力リストから重複を削除してcomb呼び出すだけです。mycomb重複を削除すると、後で 2 つの要素が「同じ」かどうかを簡単にテストできます。私があなたのメソッドに加えた唯一の変更はmycomb、メソッドが再帰的に呼び出されるときにel、リストの前に表示される要素を削除することです。これは、出力に重複がないようにするためです。

> 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))
于 2009-07-07T08:17:36.403 に答える
7

一方、組み合わせは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))

ご覧のとおり、繰り返しは許可されていませんが、組み合わせを使用することで簡単に許可できます。コレクションのすべての要素（0からli.size-1）を列挙し、リスト内の要素にマップします。

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))
于 2012-06-18T06:15:39.293 に答える
1

この問題に対する同様の解決策をブログに書きました：http：//gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-to.html

最初に、考えられるすべての組み合わせを生成して重複を削除することを考えました（または、重複自体を処理するセットを使用します）が、問題がリストで指定され、考えられるすべての組み合わせが多すぎるため、思いついたのです。問題の再帰的な解決策：

サイズnの組み合わせを取得するには、セットの1つの要素を取得し、残りの要素のサイズn-1のセットのすべての組み合わせに追加し、残りの要素のサイズnの組み合わせを結合します。それがコードの役割です

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

読み方：

リストをリストのリストに「持ち上げる」補助関数を作成する必要がありました

ロジックはmatchステートメントにあります。

リストの要素のサイズ1のすべての組み合わせが必要な場合は、各サブリストに元の要素の要素が含まれるリストのリストを作成するだけです（これが「リフト」機能です）。

組み合わせがリストの全長である場合は、要素が要素リストのみであるリストを返すだけです（可能な組み合わせは1つだけです！）

それ以外の場合は、リストの先頭と末尾を取得し、末尾のサイズn-1のすべての組み合わせを計算し（再帰呼び出し）、結果のリストのそれぞれに先頭を追加します（.map（ys.head :: zs））結果をリストの末尾のサイズnのすべての組み合わせと連結します（別の再帰呼び出し）

それは意味がありますか？

于 2009-07-02T15:19:37.720 に答える
0

このソリューションは、Rosetta Code に投稿されました: 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
于 2012-09-21T06:21:08.407 に答える
0

あなたが何を求めているのかは本当に明確ではありません。それはいくつかの異なるものの1つかもしれません。最初は、リスト内のさまざまな要素の単純な組み合わせです。Scala はcombinations()コレクションからのメソッドでそれを提供します。要素が異なる場合、その動作は、「組み合わせ」の古典的な定義から期待されるものとまったく同じです。p 個の要素の n 個の要素の組み合わせの場合、p!/n!(pn)! になります。出力の組み合わせ。

ただし、リストに要素が繰り返されている場合、Scala はその項目が複数回出現する組み合わせを生成します。ただし、要素が入力に存在する回数だけ複製される可能性のある、さまざまな可能な組み合わせだけです。可能な組み合わせのセットのみを生成するため、繰り返される要素は生成されますが、繰り返される組み合わせは生成されません。基になるものに実際のイテレータがあるかどうかはわかりませんSet。

私が正しく理解していれば、あなたが実際に意味するのは、与えられた異なる p 要素のセットからの組み合わせであり、要素は組み合わせで n 回繰り返し現れる可能性があります。

さて、少し戻って、入力に繰り返し要素があり、出力で繰り返しの組み合わせを見たい場合に組み合わせを生成するには、 n ネストされた n を使用して「ブルートフォース」で生成するだけですループします。それについては本当に野蛮なことは何もないことに注意してください。これは実際には組み合わせの自然数であり、小さな n の場合は O(p^n) であり、それについてできることは何もありません。次のように、これらの値を適切に選択するように注意する必要があります。

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

その結果

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

0 until a.sizeこれは、最初にas (i, j)...の中間の組み合わせを作成することにより、a で繰り返される値から組み合わせを生成します

「繰り返しとの組み合わせ」を作成するには、次のようにインデックスを変更するだけです。

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

生産します

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

しかし、これをより大きな組み合わせに一般化する最善の方法が何であるかはわかりません。

この投稿を見つけたときに探していたもので締めくくりますcombinations()。 . このメソッドがタプルの代わりにリストを生成するのは素晴らしいことです。つまり、「マップのマップ」を使用して実際に問題を解決できることを意味します。他の誰かがここで提案したかどうかはわかりませんが、それはかなり気の利いたものであり、これを見れば、FP と Scala への愛着がさらに増すことでしょう。

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

結果は

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))
于 2016-08-24T20:59:58.757 に答える