Cách tạo bộ nguồn của bộ trong Scala

Question

Tôi có một bộ các mục thuộc loại nào đó và muốn tạo bộ nguồn của nó.

Tôi đã tìm kiếm trên web và không thể tìm thấy bất kỳ mã Scala nào áp dụng tác vụ cụ thể này.

Đây là những gì tôi nghĩ ra. Nó cho phép bạn hạn chế cardinality của các bộ được tạo ra bởi tham số chiều dài.

def power[T](set: Set[T], length: Int) = { 
    var res = Set[Set[T]]() 
    res ++= set.map(Set(_)) 

    for (i <- 1 until length) 
     res = res.map(x => set.map(x + _)).flatten 

    res 
    } 

Điều này sẽ không bao gồm bộ trống. Để thực hiện điều này, bạn sẽ phải thay đổi dòng cuối cùng của phương thức đơn giản là res + Set()

Bất kỳ gợi ý nào có thể được thực hiện theo một phong cách chức năng hơn?

Answer 1

Chú ý rằng nếu bạn có một bộ S và một thiết T nơi T = S ∪ {x} (tức T là S với một yếu tố bổ sung) thì Powerset của T-P(T) - có thể được biểu diễn dưới dạng P(S) và x như sau:

P(T) = P(S) ∪ { p ∪ {x} | p ∈ P(S) } 

Tức là, bạn có thể xác định quyền hạn đệ quy (lưu ý cách này cung cấp cho bạn kích thước của phần tử miễn phí - tức là thêm 1 phần tử tăng gấp đôi kích thước của bộ điều khiển). Vì vậy, bạn có thể làm đuôi-đệ quy này trong scala như sau:

scala> def power[A](t: Set[A]): Set[Set[A]] = { 
    |  @annotation.tailrec 
    |  def pwr(t: Set[A], ps: Set[Set[A]]): Set[Set[A]] = 
    |  if (t.isEmpty) ps 
    |  else pwr(t.tail, ps ++ (ps map (_ + t.head))) 
    | 
    |  pwr(t, Set(Set.empty[A])) //Powerset of ∅ is {∅} 
    | } 
power: [A](t: Set[A])Set[Set[A]] 

Sau đó:

scala> power(Set(1, 2, 3)) 
res2: Set[Set[Int]] = Set(Set(1, 2, 3), Set(2, 3), Set(), Set(3), Set(2), Set(1), Set(1, 3), Set(1, 2)) 

Nó thực sự trông rất đẹp làm việc cùng với một List (tức là một ADT đệ quy):

scala> def power[A](s: List[A]): List[List[A]] = { 
    |  @annotation.tailrec 
    |  def pwr(s: List[A], acc: List[List[A]]): List[List[A]] = s match { 
    |  case Nil  => acc 
    |  case a :: as => pwr(as, acc ::: (acc map (a :: _))) 
    |  } 
    |  pwr(s, Nil :: Nil) 
    | } 
power: [A](s: List[A])List[List[A]] 

Answer 2

Sử dụng được xây dựng trong combinations chức năng:

val xs = Seq(1,2,3) 
(0 to xs.size) flatMap xs.combinations 

// Vector(List(), List(1), List(2), List(3), List(1, 2), List(1, 3), List(2, 3), 
// List(1, 2, 3)) 

Lưu ý, tôi đã lừa dối và sử dụng Seq, vì lý do không xác định, combinations được xác định trên SeqLike. Vì vậy, với một thiết lập, bạn cần phải chuyển đổi đến/từ một Seq:

val xs = Set(1,2,3) 
(0 to xs.size).flatMap(xs.toSeq.combinations).map(_.toSet).toSet 

//Set(Set(1, 2, 3), Set(2, 3), Set(), Set(3), Set(2), Set(1), Set(1, 3), 
//Set(1, 2)) 

Answer 3

Dưới đây là một trong những cách thú vị hơn để viết nó:

import scalaz._, Scalaz._ 

def powerSet[A](xs: List[A]) = xs filterM (_ => true :: false :: Nil) 

Những tác phẩm như mong đợi:

scala> powerSet(List(1, 2, 3)) foreach println 
List(1, 2, 3) 
List(1, 2) 
List(1, 3) 
List(1) 
List(2, 3) 
List(2) 
List(3) 
List() 

Xem ví dụ this discussion thread để biết cách hoạt động.

(Và như debilski ghi chú trong các ý kiến, ListW cũng Pimps powerset vào List, nhưng điều đó không có gì vui vẻ.)

Answer 4

Hình như không ai biết về nó trở lại trong tháng bảy, nhưng có một phương pháp built-in: subsets.

scala> Set(1,2,3).subsets foreach println 
Set() 
Set(1) 
Set(2) 
Set(3) 
Set(1, 2) 
Set(1, 3) 
Set(2, 3) 
Set(1, 2, 3) 

Answer 5

Đây là một (lười biếng) phiên bản ... vì chúng ta đang thu thập cách tính toán các thiết lập quyền lực, tôi nghĩ rằng tôi muốn thêm nó:

def powerset[A](s: Seq[A]) = 
    Iterator.range(0, 1 << s.length).map(i => 
    Iterator.range(0, s.length).withFilter(j => 
     (i >> j) % 2 == 1 
    ).map(s) 
) 

Answer 6

có thể đơn giản như:

def powerSet[A](xs: Seq[A]): Seq[Seq[A]] = 
    xs.foldLeft(Seq(Seq[A]())) {(sets, set) => sets ++ sets.map(_ :+ set)} 

thực hiện đệ quy:

def powerSet[A](xs: Seq[A]): Seq[Seq[A]] = { 
    def go(xsRemaining: Seq[A], sets: Seq[Seq[A]]): Seq[Seq[A]] = xsRemaining match { 
    case Nil => sets 
    case y :: ys => go(ys, sets ++ sets.map(_ :+ y)) 
    } 

    go(xs, Seq[Seq[A]](Seq[A]())) 
} 

Answer 7

Dưới đây là một giải pháp đệ quy đơn giản sử dụng một hàm helper:

def concatElemToList[A](a: A, list: List[A]): List[Any] = (a,list) match { 
    case (x, Nil)     => List(List(x)) 
    case (x, ((h:List[_]) :: t)) => (x :: h) :: concatElemToList(x, t) 
    case (x, (h::t))    => List(x, h) :: concatElemToList(x, t) 
} 

def powerSetRec[A] (a: List[A]): List[Any] = a match { 
    case Nil => List() 
    case (h::t) => powerSetRec(t) ++ concatElemToList(h, powerSetRec (t)) 
} 

nên tiếng gọi của

powerSetRec(List("a", "b", "c")) 

sẽ cho kết quả

List(List(c), List(b, c), List(b), List(a, c), List(a, b, c), List(a, b), List(a)) 

Answer 8

Tất cả các câu trả lời khác có vẻ hơi phức tạp, đây là một chức năng đơn giản:

def powerSet (l:List[_]) : List[List[Any]] = 
     l match { 
     case Nil => List(List()) 
     case x::xs => 
     var a = powerSet(xs) 
     a.map(n => n:::List(x)):::a 
     } 

nên

powerSet(List('a','b','c')) 

sẽ tạo ra kết quả sau

res0: List[List[Any]] = List(List(c, b, a), List(b, a), List(c, a), List(a), List(c, b), List(b), List(c), List())