set vs. indices - Geogi/CriojoSC GitHub Wiki

Indices

Implementation:

def combinations[T](in: List[T]): List[List[Option[T]]] = in match {
  case x :: xs => combinations(xs).map(None :: _) ::: combinations(xs).map(Some(x) :: _)
  case _ => List(Nil)
}

Results:

scala> val l = collection.mutable.ListBuffer.empty[Int]; Stream.from(1).foreach{i => l += i; println(i, combinations(l.toList).size)}
(1,2)
(2,4)
(3,8)
(4,16)
(5,32)
(6,64)
(7,128)
(8,256)
(9,512)
(10,1024)
(11,2048)
(12,4096)
(13,8192)
(14,16384)
(15,32768)
(16,65536)
(17,131072)
(18,262144)
java.lang.OutOfMemoryError: GC overhead limit exceeded

Set

Implementation:

def combinations[T](in: Set[T], sup: Set[T] = Set.empty[T], out: Set[Set[T]] = Set.empty[Set[T]]): Set[Set[T]] =
  if (in.isEmpty && sup.isEmpty) out
  else if (in.isEmpty) combinations(sup.dropRight(1), sup.tail, out + sup)
  else if (sup.isEmpty) combinations(in.dropRight(1), in.tail, out + in)
  else combinations(in.dropRight(1), sup, out + in)

Results:

scala> val s = collection.mutable.HashSet.empty[Int]; Stream.from(1).foreach{i => s += i; println(i, combinations(s.toSet).size)}
(1,1)
(2,3)
(3,6)
(4,10)
(5,15)
(6,21)
(7,28)
(8,36)
(9,45)
(10,55)
(11,66)
(12,78)
(13,91)
(14,105)
(15,120)
(16,136)
(17,153)
(18,171)
(19,190)
(20,210)
(21,231)
(22,253)
(23,276)
(24,300)
(25,325)
(26,351)
(27,378)
(28,406)
(29,435)
(30,465)
(31,496)
(32,528)
(33,561)
(34,595)
(35,630)
(36,666)
(37,703)
(38,741)
(39,780)
(40,820)
(41,861)
(42,903)
(43,946)
(44,990)
(45,1035)
(46,1081)
(47,1128)
(48,1176)
(49,1225)
(50,1275)
(51,1326)
(52,1378)
(53,1431)
(54,1485)
(55,1540)
(56,1596)
(57,1653)
(58,1711)
(59,1770)
(60,1830)
(61,1891)
(62,1953)
(63,2016)
(64,2080)
(65,2145)
(66,2211)
(67,2278)
(68,2346)
(69,2415)
(70,2485)
(71,2556)
(72,2628)
(73,2701)
(74,2775)
(75,2850)
(76,2926)
(77,3003)
(78,3081)
(79,3160)
(80,3240)
(81,3321)
(82,3403)
(83,3486)
(84,3570)
(85,3655)
(86,3741)
(87,3828)
(88,3916)
(89,4005)
(90,4095)
(91,4186)
(92,4278)
(93,4371)
(94,4465)
(95,4560)
(96,4656)
(97,4753)
(98,4851)
(99,4950)
(100,5050)
(101,5151)
(102,5253)
(103,5356)
(104,5460)
(105,5565)
(106,5671)
(107,5778)
(108,5886)
(109,5995)
(110,6105)
(111,6216)
(112,6328)
(113,6441)
(114,6555)
(115,6670)
(116,6786)
(117,6903)
(118,7021)
(119,7140)
(120,7260)
(121,7381)
(122,7503)
(123,7626)
(124,7750)
(125,7875)
(126,8001)
(127,8128)
(128,8256)
(129,8385)
(130,8515)
(131,8646)
(132,8778)
(133,8911)
(134,9045)
(135,9180)
(136,9316)
(137,9453)
(138,9591)
(139,9730)
(140,9870)
(141,10011)
(142,10153)
(143,10296)
(144,10440)
(145,10585)
(146,10731)
(147,10878)
(148,11026)
(149,11175)
(150,11325)
(151,11476)
(152,11628)
(153,11781)
(154,11935)
(155,12090)
(156,12246)
(157,12403)
(158,12561)
(159,12720)
(160,12880)
(161,13041)
(162,13203)
(163,13366)
(164,13530)
(165,13695)
(166,13861)
(167,14028)
(168,14196)
(169,14365)
(170,14535)
(171,14706)
(172,14878)
(173,15051)
(174,15225)
(175,15400)
(176,15576)
(177,15753)
(178,15931)
(179,16110)
(180,16290)
(181,16471)
(182,16653)
(183,16836)
(184,17020)
(185,17205)
(186,17391)
(187,17578)
(188,17766)
(189,17955)
(190,18145)
(191,18336)
(192,18528)
(193,18721)
(194,18915)
(195,19110)
(196,19306)
(197,19503)
(198,19701)
(199,19900)
(200,20100)
(201,20301)
(202,20503)
(203,20706)
(204,20910)
(205,21115)
(206,21321)
(207,21528)
(208,21736)
(209,21945)
(210,22155)
(211,22366)
(212,22578)
(213,22791)
(214,23005)
(215,23220)
(216,23436)
(217,23653)
(218,23871)
(219,24090)
(220,24310)
(221,24531)
(222,24753)
(223,24976)
(224,25200)
(225,25425)
(226,25651)
(227,25878)
(228,26106)
(229,26335)
(230,26565)
(231,26796)
(232,27028)
(233,27261)
(234,27495)
(235,27730)
(236,27966)
(237,28203)
(238,28441)
(239,28680)
(240,28920)
(241,29161)
(242,29403)
(243,29646)
(244,29890)
(245,30135)
(246,30381)
(247,30628)
(248,30876)
(249,31125)
(250,31375)
(251,31626)
(252,31878)
(253,32131)
(254,32385)
(255,32640)
(256,32896)
(257,33153)
(258,33411)
(259,33670)
(260,33930)
(261,34191)
(262,34453)
(263,34716)
(264,34980)
(265,35245)
(266,35511)
(267,35778)
(268,36046)
(269,36315)
(270,36585)
(271,36856)
(272,37128)
(273,37401)
(274,37675)
(275,37950)
(276,38226)
(277,38503)
(278,38781)
(279,39060)
(280,39340)
(281,39621)
(282,39903)
(283,40186)
(284,40470)
(285,40755)
(286,41041)
(287,41328)
(288,41616)
(289,41905)
(290,42195)
(291,42486)
(292,42778)
(293,43071)
(294,43365)
(295,43660)
(296,43956)
(297,44253)
(298,44551)
(299,44850)
(300,45150)
(301,45451)
(302,45753)
(303,46056)
(304,46360)
(305,46665)
(306,46971)
(307,47278)
(308,47586)
(309,47895)
(310,48205)
(311,48516)
(312,48828)
(313,49141)
(314,49455)
(315,49770)
(316,50086)
java.lang.OutOfMemoryError: Java heap space