Permutations with repetitions: Difference between revisions
→{{header|Python}}: Added a variant with a hand-written generator
(→JS Lazy evaluation with a generator: Replaced code with correct version) |
(→{{header|Python}}: Added a variant with a hand-written generator) |
||
Line 1,577:
print w
if w.lower() == 'crack': break</lang>
Or, composing our own generator, by wrapping a function '''from''' an index in the range ''0 .. (distinct items to the power of groupSize)'' '''to''' a unique permutation. (Each permutation is equivalent to a 'number' in the base of the size of the set of distinct items, in which each distinct item functions as a 'digit'):
<lang Python>from functools import (reduce)
from itertools import (repeat)
# main :: IO ()
def main():
cs = 'ACKR'
wordLength = 5
gen = permutesWithRepns(cs)(wordLength)
for idx, xs in enumerate(gen):
s = ''.join(xs)
if 'crack' == s.lower():
break
print (
'Permutation ' + str(idx) + ' of ' +
str(len(cs)**wordLength) + ':', s
)
# permutesWithRepns :: [a] -> Int -> Generator [[a]]
def permutesWithRepns(xs):
def groupsOfSize(n):
f = nthPermWithRepn(xs)(n)
limit = len(xs)**n
i = 0
while (i < limit):
yield f(i)
i = 1 + i
return lambda n: groupsOfSize(n)
# Index as a 'number' in the base of the
# size of the set (of distinct values to be permuted),
# using each value as a 'digit'
# (leftmost value used as the 'zero')
# nthPermWithRepn :: [a] -> Int -> Int -> [a]
def nthPermWithRepn(xs):
def go(intGroup, index):
vs = list(xs)
intBase = len(vs)
intSet = intBase ** intGroup
return (
lambda ds=unfoldr(lambda v: (
(lambda qr=divmod(v, intBase):
Just((vs[qr[1]], qr[0])))()
) if 0 < v else Nothing()
)(index): (
list(repeat(vs[0], intGroup - len(ds))) + ds
)
)() if 0 < intBase and index < intSet else None
return lambda intGroup: lambda index: go(
intGroup, index
)
# GENERIC FUNCTIONS -------------------------------------
# Just :: a -> Maybe a
def Just(x):
return {type: 'Maybe', 'Nothing': False, 'Just': x}
# Nothing :: Maybe a
def Nothing():
return {type: 'Maybe', 'Nothing': True}
# concat :: [[a]] -> [a]
def concat(xs):
return (
reduce(
lambda a, b: a + b, xs,
'' if type(xs[0]) is str else []
) if xs else []
)
# unfoldr(lambda x: Just((x, x - 1)) if 0 != x else Nothing(), 10)]
# -> [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
# unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
def unfoldr(f):
def go(v):
xr = (v, v)
xs = []
while True:
mb = f(xr[1])
if mb.get('Nothing'):
return xs
else:
xr = mb.get('Just')
xs.append(xr[0])
return xs
return lambda v: go(v)
main()</lang>
{{Out}}
<pre>Permutation 589 of 1024: CRACK</pre>
=={{header|Racket}}==
| |||