add powerset.HEADmaster

1 files changed, 35 insertions, 1 deletions

diff --git a/czzc/iter.lua b/czzc/iter.lua
index 866b43a..53cc46a 100644
--- a/czzc/iter.lua
+++ b/czzc/iter.lua
@@ -116,6 +116,40 @@ M.words = function(str)
     end
 end
 
+-- iterate lazily over the power set of an array.
+-- returns arrays, including the empty array.
+M.powerset = function(arr)
+    local bits = {}
+    for i=1, #arr do 
+        table.insert(bits, 0)
+    end
+    local done = false
+    local i = 0
+    return function()
+        i = i + 1
+        if not done then
+            local res = {}
+            for j=1, #arr do
+                if bits[j] == 1 then
+                    table.insert(res, arr[j])
+                end
+            end
+            for b=1, #bits do
+                if bits[b] == 0 then
+                    bits[b] = 1
+                    break
+                else
+                    bits[b] = 0
+                    if b == #bits then
+                        done = true
+                    end
+                end
+            end
+            return res
+        end
+    end
+end
+
 -- cool, right?
 M.bytes = M.apply_factory(string.byte, M.chars, 1)
 
@@ -143,7 +177,7 @@ M.ipairs_rev = M.reverse_factory(ipairs)
 local to_be_reversed = {
     "chars",
     "bytes",
-    "words"
+    "words",
 }
 
 for _, v in ipairs(to_be_reversed) do