helper: count permutations

8 files changed, 400 insertions, 10 deletions

diff --git a/anagrams.tlv b/anagrams.tlv
index d4ffc81..e0bc818 100644
--- a/anagrams.tlv
+++ b/anagrams.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   menu:
     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
     >-- arrays of strings to the menu array.
@@ -510,16 +560,6 @@
     >  return result
     >end
 - __teliva_timestamp:
-    >Sat Mar  5 15:24:34 2022
-  factorial:
-    >function factorial(n)
-    >  local result = 1
-    >  for i=1,n do
-    >    result = result*i
-    >  end
-    >  return result
-    >end
-- __teliva_timestamp:
     >Sat Mar  5 15:53:23 2022
   key_pressed:
     >-- only works when nodelay (non-blocking keyboard)
diff --git a/break.tlv b/break.tlv
index 36041e6..8b2e9b1 100644
--- a/break.tlv
+++ b/break.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   menu:
     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
     >-- arrays of strings to the menu array.
diff --git a/gemini.tlv b/gemini.tlv
index f661a21..15e16f8 100644
--- a/gemini.tlv
+++ b/gemini.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   Window:
     >Window = curses.stdscr()
 - __teliva_timestamp: original
diff --git a/graphviz.tlv b/graphviz.tlv
index 18fb7e0..bed0808 100644
--- a/graphviz.tlv
+++ b/graphviz.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   menu:
     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
     >-- arrays of strings to the menu array.
diff --git a/life.tlv b/life.tlv
index eba123f..03307f5 100644
--- a/life.tlv
+++ b/life.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   menu:
     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
     >-- arrays of strings to the menu array.
diff --git a/template.tlv b/template.tlv
index 829c4ab..bf092d0 100644
--- a/template.tlv
+++ b/template.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   menu:
     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
     >-- arrays of strings to the menu array.
diff --git a/toot-toot.tlv b/toot-toot.tlv
index 375d503..bb5ea56 100644
--- a/toot-toot.tlv
+++ b/toot-toot.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   menu:
     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
     >-- arrays of strings to the menu array.
diff --git a/zet.tlv b/zet.tlv
index fcc66a8..9f81dee 100644
--- a/zet.tlv
+++ b/zet.tlv
@@ -381,6 +381,56 @@
     >  append(target, src)
     >end
 - __teliva_timestamp: original
+  mfactorial:
+    >-- memoized version of factorial
+    >-- doesn't memoize recursive calls, but may be good enough
+    >mfactorial = memo1(factorial)
+- __teliva_timestamp: original
+  factorial:
+    >function factorial(n)
+    >  local result = 1
+    >  for i=1,n do
+    >    result = result*i
+    >  end
+    >  return result
+    >end
+- __teliva_timestamp: original
+  memo1:
+    >-- a higher-order function that takes a function of a single arg
+    >-- (that never returns nil)
+    >-- and returns a memoized version of it
+    >function memo1(f)
+    >  local memo = {}
+    >  return function(x)
+    >    if memo[x] == nil then
+    >      memo[x] = f(x)
+    >    end
+    >    return memo[x]
+    >  end
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
+    >  end
+    >end
+- __teliva_timestamp: original
+  num_permutations:
+    >-- number of permutations of n distinct objects, taken r at a time
+    >function num_permutations(n, r)
+    >  return factorial(n)/factorial(n-r)
+    >end
+    >
+    >-- mfactorial doesn't seem noticeably faster
+    >function test_memo1()
+    >  for i=0,30 do
+    >    for j=0,i do
+    >      check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
+    >    end
+    >  end
+    >end
+- __teliva_timestamp: original
   menu:
     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
     >-- arrays of strings to the menu array.