Kết hợp danh sách VỚI sự lặp lại trong Scala

Question

Cố gắng tìm hiểu một chút Scala và gặp phải vấn đề này. Tôi đã tìm thấy giải pháp cho tất cả các kết hợp không có sự lặp lại here và tôi phần nào hiểu được ý tưởng đằng sau nó nhưng một số cú pháp làm tôi rối tung lên. Tôi cũng không nghĩ giải pháp phù hợp với trường hợp lặp lại. Tôi đã tự hỏi nếu có ai có thể gợi ý một chút mã mà tôi có thể làm việc. Tôi có rất nhiều tài liệu về tổ hợp và hiểu được vấn đề và các giải pháp lặp đi lặp lại cho nó, tôi chỉ đang tìm kiếm cách thức thực hiện.

Cảm ơn

Answer 1

Tôi hiểu câu hỏi của bạn ngay bây giờ. Tôi nghĩ rằng cách dễ nhất để đạt được những gì bạn muốn là phải làm như sau:

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) 

Phương pháp comb chỉ gọi mycomb với bản sao ra khỏi danh sách đầu vào. Loại bỏ các bản sao có nghĩa là nó sau đó dễ dàng hơn để kiểm tra sau này cho dù hai yếu tố là 'giống nhau'.Sự thay đổi duy nhất tôi đã thực hiện cho phương pháp mycomb của bạn là khi phương pháp này được gọi là đệ quy, tôi loại bỏ các phần tử xuất hiện trước el trong danh sách. Điều này là để ngăn chặn có được bản sao trong đầu ra.

> 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

Câu hỏi được lặp lại trong một trong những câu trả lời - Tôi hy vọng bản thân câu hỏi cũng được chỉnh sửa. Một người khác đã trả lời câu hỏi thích hợp. Tôi sẽ để lại mã dưới đây trong trường hợp ai đó thấy nó hữu ích.

Giải pháp đó khó hiểu là địa ngục. Một "kết hợp" không lặp lại được gọi là hoán vị. Nó có thể giống như sau:

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 
    } 

Nếu danh sách đầu vào không được đảm bảo chứa các phần tử duy nhất, như được đề xuất trong câu trả lời khác, có thể khó hơn một chút. Thay vì lọc, loại bỏ tất cả các phần tử, chúng ta cần phải loại bỏ phần tử đầu tiên.

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 
} 

Chỉ cần giải thích một chút. Trong đó, chúng tôi lấy từng phần tử của danh sách và trả về các danh sách bao gồm nó theo sau là hoán vị của tất cả các phần tử trong danh sách ngoại trừ phần tử đã chọn.

Ví dụ: nếu chúng tôi lấy Danh sách (1,2,3), chúng tôi sẽ tạo danh sách được tạo thành bởi 1 và perm (Danh sách (2,3)), 2 và perm (Danh sách (1,3)) và 3 và perm (Danh sách (1,2)).

Vì chúng tôi đang thực hiện hoán vị có kích thước tùy ý, chúng tôi theo dõi thời gian mỗi subpermutation có thể được bao lâu. Nếu một subpermutation là kích thước 0, điều quan trọng là chúng ta trả về một danh sách chứa một danh sách rỗng. Lưu ý rằng đây không phải là một danh sách trống! Nếu chúng ta trả về Nil trong trường hợp 0, sẽ không có phần tử nào cho sl trong perm gọi, và toàn bộ "for" sẽ sinh ra Nil. Bằng cách này, sl sẽ được gán Nil, và chúng ta sẽ soạn một danh sách el :: Nil, yielding List (el).

Tôi đã suy nghĩ về vấn đề ban đầu, tuy nhiên, và tôi sẽ đăng giải pháp của tôi ở đây để tham khảo. Nếu bạn có nghĩa là không có các phần tử trùng lặp trong câu trả lời do kết quả của các phần tử trùng lặp trong đầu vào, chỉ cần thêm một removeDuplicates như được hiển thị bên dưới.

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 
} 

Đó là một chút xấu xí, tôi biết. Tôi phải sử dụng toList để chuyển đổi phạm vi (trả về bởi "thành") thành một Danh sách, do đó, "cho" chính nó sẽ trả về một Danh sách. Tôi có thể làm với "l1", nhưng tôi nghĩ điều này làm rõ hơn những gì tôi đang làm.Vì không có bộ lọc ở đây, sửa đổi nó để loại bỏ các bản sao được dễ dàng hơn nhiều:

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 - Tôi không chắc chắn những gì Alex nghĩa bản sao, nó có thể là những điều sau đây cung cấp một câu trả lời thích hợp hơn:

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 
} 

Run as

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

này cung cấp cho:

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

như trái ngược với:

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

Các nastiness bên trong gọi perm lồng nhau được loại bỏ một đơn 'el' từ danh sách, tôi tưởng tượng có một cách đẹp hơn để làm điều đó nhưng tôi không thể nghĩ ra một .

Answer 4

Tôi đã viết một giải pháp tương tự cho các vấn đề trong blog của tôi: http://gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-to.html

Trước tiên tôi nghĩ đến việc tạo ra tất cả các kết hợp có thể và loại bỏ các bản sao, (hoặc sử dụng bộ, mà sẽ chăm sóc của sự trùng lặp chính nó) nhưng như vấn đề đã được chỉ định với danh sách và tất cả các kết hợp có thể sẽ là quá nhiều, tôi đã đưa ra giải pháp đệ quy cho sự cố:

để lấy kết hợp kích thước n, lấy một phần của tập hợp và thêm vào cho tất cả các tổ hợp các tập hợp kích thước n-1 của các phần tử còn lại, kết hợp các kích thước n của các phần tử còn lại. Đó là những gì các mã không

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

Làm thế nào để đọc nó:

tôi đã phải tạo ra một chức năng phụ trợ mà "nâng đỡ" một danh sách vào một danh sách liệt kê

Logic là trong trận đấu tuyên bố:

Nếu bạn muốn tất cả các kết hợp của kích thước 1 của các phần tử trong danh sách, chỉ cần tạo danh sách các danh sách phụ chứa một phần tử gốc (đó là chức năng "nâng")

Nếu kết hợp là tổng chiều dài của danh sách, chỉ cần trả về danh sách trong đó yếu tố duy nhất là danh sách phần tử (chỉ có một kết hợp có thể!)

Nếu không, hãy lấy đầu và đuôi của danh sách, tính toán tất cả các kết hợp của kích thước n-1 của đuôi (gọi đệ quy) và nối đầu vào mỗi danh sách kết quả (.map (ys.head :: zs)) nối kết quả với tất cả các kết hợp của kích thước n của đuôi của danh sách (một cuộc gọi đệ quy khác)

Có hợp lý không?

Answer 5

Trong khi đó, kết hợp đã trở thành một phần không thể thiếu trong bộ sưu tập 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)) 

Như chúng ta thấy, nó không cho phép lặp lại, nhưng cho phép họ rất đơn giản với sự kết hợp mặc dù: Liệt kê tất cả các yếu tố bộ sưu tập của bạn (0 đến li.size-1) và bản đồ đến phần tử trong danh sách:

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

giải pháp này đã được đăng trên 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 

Answer 7

Nó thực sự không rõ ràng những gì bạn đang yêu cầu. Nó có thể là một trong vài điều khác nhau. Đầu tiên sẽ là sự kết hợp đơn giản của các yếu tố khác nhau trong một danh sách. Scala cung cấp phương thức combinations() từ các bộ sưu tập. Nếu các phần tử là khác biệt, hành vi chính xác là những gì bạn mong đợi từ định nghĩa cổ điển của "kết hợp". Đối với kết hợp phần tử n của các phần tử p sẽ có p!/N! (P-n)! kết hợp trong đầu ra.

Nếu có các yếu tố lặp lại trong danh sách, tuy nhiên, Scala sẽ tạo kết hợp với mục xuất hiện nhiều lần trong các kết hợp. Nhưng chỉ các kết hợp có thể khác nhau, với phần tử có thể được sao chép nhiều lần khi chúng tồn tại trong đầu vào. Nó chỉ tạo ra tập hợp các kết hợp có thể, do đó các phần tử được lặp lại, nhưng không phải là các kết hợp lặp lại. Tôi không chắc chắn nếu cơ bản nó có một iterator đến một thực tế Set. Bây giờ điều bạn thực sự muốn nói nếu tôi hiểu chính xác là các kết hợp từ một tập hợp các phần tử p khác nhau, trong đó phần tử có thể xuất hiện nhiều lần n lần trong tổ hợp.

Vâng, quay lại một chút, để tạo kết hợp khi có các yếu tố lặp lại trong đầu vào và bạn muốn xem kết hợp lặp lại trong đầu ra, cách để thực hiện nó là tạo ra nó bằng "brute-force "sử dụng n vòng lặp lồng nhau. Lưu ý rằng thực sự không có gì xấu về nó, nó chỉ là số kết hợp tự nhiên, thực sự, đó là O (p^n) cho n nhỏ, và không có gì bạn có thể làm về nó. Bạn chỉ nên cẩn thận để chọn các giá trị đúng cách, như thế này:

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

dẫn đến

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

này tạo ra các kết hợp từ những giá trị này lặp đi lặp lại trong một, bằng cách đầu tiên tạo ra các kết hợp trung gian của 0 until a.size như (i, j) ...

Bây giờ để tạo "kết hợp với lặp lại", bạn chỉ cần thay đổi các chỉ mục như sau:

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

sẽ sản xuất

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

Nhưng tôi không chắc chắn cách tốt nhất để khái quát này để kết hợp lớn hơn là những gì.

Bây giờ tôi đóng với những gì tôi đang tìm kiếm khi tôi tìm thấy bài đăng này: một hàm để tạo kết hợp từ đầu vào chứa các phần tử lặp lại, với chỉ số trung gian được tạo bởi combinations(). Nó là tốt đẹp mà phương pháp này tạo ra một danh sách thay vì một tuple, do đó có nghĩa là chúng tôi thực sự có thể giải quyết vấn đề bằng cách sử dụng một "bản đồ của một bản đồ", một cái gì đó tôi không chắc chắn bất cứ ai khác đã đề xuất ở đây, nhưng đó là khá tiện lợi và sẽ làm cho tình yêu của bạn cho FP và Scala phát triển hơn một chút sau khi bạn nhìn thấy nó!

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

kết quả trong

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