Project P084
Permutations and combinations
The orderings of a word's letters by backtracking and in dictionary order, with repeated letters counted once; the next and previous ordering; an ordering's place and the ordering at a place; combinations; derangements, whose share closes in on 1/e; and Gray codes.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
The orderings of a word's letters, by backtracking and in dictionary order, with repeated letters counted once. Also: the next and previous ordering; an ordering's place among all of them and the ordering at a given place; combinations; derangements, whose share closes in on 1/e; and Gray codes.
main.eml- the menu, reading words and numbers, and the reportsarrange.eml- backtracking, counting different words, next and previous orderings, rank and unrank, combinations, derangements, Gray codes
How each part works:
- Backtracking, as in the corpus case
permutations-generator: pick an unused item, go on with the rest, then free it again for the next branch. The list of used items is changed in place, so it must be undone; the ordering so far is a new list each time, so it need not be. It makes all n! orderings, repeats included: 720 for "banana". - Dictionary order: the next ordering finds the rightmost place where an item is smaller than the one after it, swaps it with the rightmost bigger item, and reverses the rest. Starting from the sorted letters, that lists each different word exactly once - 60 for "banana", which is 6! / (3! 2!).
- An ordering's place: for each position, count the smaller items still to come and multiply by the orderings of the rest (the factorial number system). The ordering at a place reads the same digits back.
- Derangements, the orderings that leave nothing in its place: D(n) = (n - 1)(D(n - 1) + D(n - 2)). Their share of all orderings closes in on 1/e: D(10)/10! = 0.3678794..., against 1/e = 0.3678794411...
- Gray code: the (n - 1)-bit code, then the same reversed, with 0 and then 1 in front. Each code differs from the one before in one bit, so the subsets come one item in or out at a time.
What is checked: menu choices 1 to 8; words of letters or digits, up to 6 for listing orderings, 12 for neighbours and places, 10 for combinations, 5 for Gray codes, with all items different where a place or a subset needs it; a place from 1 to n!; 0 to n items to choose; n from 1 to 20 for derangements. An empty answer cancels.
Sessions: sessions/basic.in gives: - the orderings of abc and of banana (720 made, 60 different); - the neighbours of monday, and of abc (the first) and cba (the last); - monday as number 327 of 720, ordering 327 of admnoy, and ordering 24 of abcd (dcba); - 3 of 5 items (10 ways) and 0 of 5 (1 way); - derangements of 3 and of 10, and the Gray code for abc.
sessions/bad-input.in gives: - menu choices 0 and x; - a 7-letter word, "a b", a word with a repeated letter where they must differ, place 7 of 6, 11 items, choosing 4 of 3, n of 0 and 21, and 6 items for a Gray code - each refused, then cancelled.
Built on the verified corpus case permutations-generator (backtracking, with one kind of state undone and the other rebuilt).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Permutations and combinations ==
Orderings, dictionary order, places, combinations, derangements and Gray codes.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 0
Pick a number from 1 to 8.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> x
Pick a number from 1 to 8.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 1
word (1 to 6 letters)> abcdefg
Type 1 to 6 letters or digits.
word (1 to 6 letters)> a b
Type 1 to 6 letters or digits.
word (1 to 6 letters)>
Cancelled.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 3
word with different letters (1 to 12)> hello
Type 1 to 12 letters or digits, all different.
word with different letters (1 to 12)>
Cancelled.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 4
letters, all different (1 to 12)> abc
place (1 to 6)> 7
Type a whole number from 1 to 6.
place (1 to 6)>
Cancelled.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 5
items, all different (1 to 10)> abcdefghijk
Type 1 to 10 letters or digits, all different.
items, all different (1 to 10)> aab
Type 1 to 10 letters or digits, all different.
items, all different (1 to 10)> abc
how many to choose (0 to 3)> 4
Type a whole number from 0 to 3.
how many to choose (0 to 3)>
Cancelled.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 6
n (1 to 20)> 0
Type a whole number from 1 to 20.
n (1 to 20)> 21
Type a whole number from 1 to 20.
n (1 to 20)>
Cancelled.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 7
items for the subsets (1 to 5)> abcdef
Type 1 to 5 letters or digits, all different.
items for the subsets (1 to 5)>
Cancelled.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 8
Bye.
What was typed (27 lines)
0
x
1
abcdefg
a b
3
hello
4
abc
7
5
abcdefghijk
aab
abc
4
6
0
21
7
abcdef
8
basic
interpreter: byte-equal== Permutations and combinations ==
Orderings, dictionary order, places, combinations, derangements and Gray codes.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 1
word (1 to 6 letters)> abc
abc acb bac bca cab cba
Backtracking makes 6 orderings = 3!; 6 of them are different words, and stepping to the next in dictionary order lists exactly 6.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 1
word (1 to 6 letters)> banana
aaabnn aaanbn aaannb aabann aabnan aabnna aanabn aananb aanban aanbna aannab aannba abaann abanan abanna abnaan abnana abnnaa anaabn anaanb anaban anabna ananab ananba ... (36 more)
Backtracking makes 720 orderings = 6!; 60 of them are different words, and stepping to the next in dictionary order lists exactly 60.
Repeated letters make the same word more than once: n! divided by k! for each letter used k times.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 2
word (1 to 12 letters)> monday
before monday: monayd
after monday: mondya
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 2
word (1 to 12 letters)> abc
abc is the first ordering of its letters; nothing comes before it.
after abc: acb
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 2
word (1 to 12 letters)> cba
before cba: cab
cba is the last ordering of its letters; nothing comes after it.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 3
word with different letters (1 to 12)> monday
monday is number 327 of the 720 orderings of its letters, in dictionary order.
Number 327 read back the other way is monday.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 4
letters, all different (1 to 12)> admnoy
place (1 to 720)> 327
Ordering number 327 of admnoy is monday.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 4
letters, all different (1 to 12)> abcd
place (1 to 24)> 24
Ordering number 24 of abcd is dcba.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 5
items, all different (1 to 10)> abcde
how many to choose (0 to 5)> 3
abc abd abe acd ace ade bcd bce bde cde
10 ways = 5! / (3! 2!).
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 5
items, all different (1 to 10)> abcde
how many to choose (0 to 5)> 0
(none)
1 way = 5! / (0! 5!).
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 6
n (1 to 20)> 3
Of the 6 orderings of 3 things, 2 leave none in its place.
That is 0.333333333333 of them; 1/e is 0.367879441171..., which the share closes in on as n grows.
Each count is (n - 1) x (the two before added): the first thing goes to one of n - 1 places, and then it either swaps or does not.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 6
n (1 to 20)> 10
Of the 3628800 orderings of 10 things, 1334961 leave none in its place.
That is 0.367879464285 of them; 1/e is 0.367879441171..., which the share closes in on as n grows.
Each count is (n - 1) x (the two before added): the first thing goes to one of n - 1 places, and then it either swaps or does not.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 7
items for the subsets (1 to 5)> abc
000 (none)
001 c
011 bc
010 b
110 ab
111 abc
101 ac
100 a
All 8 subsets, each one item in or out from the one before - the Gray code.
1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit
choice> 8
Bye.
What was typed (31 lines)
1
abc
1
banana
2
monday
2
abc
2
cba
3
monday
4
admnoy
327
4
abcd
24
5
abcde
3
5
abcde
0
6
3
6
10
7
abc
8
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P084 permutations and combinations: the orderings of a word's letters,
# the next and previous in dictionary order, an ordering's place and the
# ordering at a place, combinations, derangements and Gray codes.
import arrange
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def number(s):
if len(s) == 0 or len(s) > 9:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def letters(s):
[] => out
for c in s:
out + [c] => out
return out
def word(xs):
"" => s
for x in xs:
s + x => s
return s
def good(s, most):
if len(s) == 0 or len(s) > most:
return False
for c in s:
if not ((c >= "a" and c <= "z") or (c >= "A" and c <= "Z") or (c >= "0" and c <= "9")):
return False
return True
def all_different(s):
for i in [0:len(s) - 1]:
for j in [i + 1:len(s) - 1]:
if s[i] == s[j]:
return False
return True
def ask_word(prompt, most, different):
while True:
trim(input(prompt)) => s
if s == "":
return ""
if good(s, most) and (not different or all_different(s)):
return s
if different:
("Type 1 to " + str(most) + " letters or digits, all different.") ^0
else:
("Type 1 to " + str(most) + " letters or digits.") ^0
def ask(prompt, low, high):
while True:
trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => a
if a == "":
return -1
number(a) => n
if n >= low and n <= high:
return n
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
def orderings():
ask_word("word (1 to 6 letters)> ", 6, False) => s
if s == "":
"Cancelled." ^0
return
letters(s) => xs
[0] * len(xs) => used
arrange.permute(xs, [], used, []) => every
arrange.distinct(xs) => d
arrange.sorted_copy(xs) => p
[] => shown
0 => count
while len(p) > 0:
if count < 24:
shown + [word(p)] => shown
count + 1 => count
arrange.next_perm(p) => p
"" => line
for w in shown:
if line != "":
line + " " => line
line + w => line
if count > 24:
line + " ... (" + str(count - 24) + " more)" => line
line ^0
("Backtracking makes " + str(len(every)) + " orderings = " + str(len(xs)) + "!; " + str(d) + " of them are different words, and stepping to the next in dictionary order lists exactly " + str(count) + ".") ^0
if d < len(every):
"Repeated letters make the same word more than once: n! divided by k! for each letter used k times." ^0
def neighbours():
ask_word("word (1 to 12 letters)> ", 12, False) => s
if s == "":
"Cancelled." ^0
return
letters(s) => xs
arrange.next_perm(xs) => n
arrange.prev_perm(xs) => p
if len(p) == 0:
(s + " is the first ordering of its letters; nothing comes before it.") ^0
else:
("before " + s + ": " + word(p)) ^0
if len(n) == 0:
(s + " is the last ordering of its letters; nothing comes after it.") ^0
else:
("after " + s + ": " + word(n)) ^0
def place():
ask_word("word with different letters (1 to 12)> ", 12, True) => s
if s == "":
"Cancelled." ^0
return
letters(s) => xs
arrange.rank(xs) => r
arrange.factorial(len(xs)) => total
(s + " is number " + str(r) + " of the " + str(total) + " orderings of its letters, in dictionary order.") ^0
arrange.unrank(xs, r) => back
("Number " + str(r) + " read back the other way is " + word(back) + ".") ^0
def at_place():
ask_word("letters, all different (1 to 12)> ", 12, True) => s
if s == "":
"Cancelled." ^0
return
arrange.factorial(len(s)) => total
ask("place", 1, total) => k
if k == -1:
"Cancelled." ^0
return
arrange.unrank(letters(s), k) => w
("Ordering number " + str(k) + " of " + word(arrange.sorted_copy(letters(s))) + " is " + word(w) + ".") ^0
def choose():
ask_word("items, all different (1 to 10)> ", 10, True) => s
if s == "":
"Cancelled." ^0
return
ask("how many to choose", 0, len(s)) => k
if k == -1:
"Cancelled." ^0
return
arrange.combinations(letters(s), k, 0, [], []) => cs
"" => line
0 => i
for c in cs:
if i < 30:
if line != "":
line + " " => line
if len(c) == 0:
line + "(none)" => line
else:
line + word(c) => line
i + 1 => i
if len(cs) > 30:
line + " ... (" + str(len(cs) - 30) + " more)" => line
line ^0
"ways" => w
if len(cs) == 1:
"way" => w
(str(len(cs)) + " " + w + " = " + str(len(s)) + "! / (" + str(k) + "! " + str(len(s) - k) + "!).") ^0
def decimal(a, b, places):
# a / b to `places` decimals, cut off, by long division (0 <= a < b).
"0." => s
a => r
for i in [1:places]:
r * 10 => r
0 => d
while r >= b:
r - b => r
d + 1 => d
s + str(d) => s
return s
def mixed_up():
ask("n", 1, 20) => n
if n == -1:
"Cancelled." ^0
return
arrange.derangements(n) => d
arrange.factorial(n) => f
("Of the " + str(f) + " orderings of " + str(n) + " things, " + str(d) + " leave none in its place.") ^0
("That is " + decimal(d, f, 12) + " of them; 1/e is 0.367879441171..., which the share closes in on as n grows.") ^0
"Each count is (n - 1) x (the two before added): the first thing goes to one of n - 1 places, and then it either swaps or does not." ^0
def gray_code():
ask_word("items for the subsets (1 to 5)> ", 5, True) => s
if s == "":
"Cancelled." ^0
return
arrange.gray(len(s)) => codes
for c in codes:
"" => sub
for i in [0:len(s) - 1]:
if c[i] == "1":
sub + s[i] => sub
if sub == "":
"(none)" => sub
(" " + c + " " + sub) ^0
("All " + str(len(codes)) + " subsets, each one item in or out from the one before - the Gray code.") ^0
"== Permutations and combinations ==" ^0
"Orderings, dictionary order, places, combinations, derangements and Gray codes." ^0
True => running
while running:
"" ^0
"1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
orderings()
elif choice == "2":
neighbours()
elif choice == "3":
place()
elif choice == "4":
at_place()
elif choice == "5":
choose()
elif choice == "6":
mixed_up()
elif choice == "7":
gray_code()
elif choice == "8":
False => running
else:
"Pick a number from 1 to 8." ^0
"Bye." ^0
Python projection (main.py)
import arrange
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def number(s):
if len(s) == 0 or len(s) > 9:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def letters(s):
out = []
for c in s:
out = out + [c]
return out
def word(xs):
s = ""
for x in xs:
s = s + x
return s
def good(s, most):
if len(s) == 0 or len(s) > most:
return False
for c in s:
if not (c >= "a" and c <= "z" or c >= "A" and c <= "Z" or c >= "0" and c <= "9"):
return False
return True
def all_different(s):
for i in range(0, len(s)):
for j in range(i + 1, len(s)):
if s[i] == s[j]:
return False
return True
def ask_word(prompt, most, different):
while True:
s = trim(input(prompt))
if s == "":
return ""
if good(s, most) and (not different or all_different(s)):
return s
if different:
print("Type 1 to " + str(most) + " letters or digits, all different.")
else:
print("Type 1 to " + str(most) + " letters or digits.")
def ask(prompt, low, high):
while True:
a = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
if a == "":
return -1
n = number(a)
if n >= low and n <= high:
return n
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
def orderings():
s = ask_word("word (1 to 6 letters)> ", 6, False)
if s == "":
print("Cancelled.")
return
xs = letters(s)
used = [0] * len(xs)
every = arrange.permute(xs, [], used, [])
d = arrange.distinct(xs)
p = arrange.sorted_copy(xs)
shown = []
count = 0
while len(p) > 0:
if count < 24:
shown = shown + [word(p)]
count = count + 1
p = arrange.next_perm(p)
line = ""
for w in shown:
if line != "":
line = line + " "
line = line + w
if count > 24:
line = line + " ... (" + str(count - 24) + " more)"
print(line)
print("Backtracking makes " + str(len(every)) + " orderings = " + str(len(xs)) + "!; " + str(d) + " of them are different words, and stepping to the next in dictionary order lists exactly " + str(count) + ".")
if d < len(every):
print("Repeated letters make the same word more than once: n! divided by k! for each letter used k times.")
def neighbours():
s = ask_word("word (1 to 12 letters)> ", 12, False)
if s == "":
print("Cancelled.")
return
xs = letters(s)
n = arrange.next_perm(xs)
p = arrange.prev_perm(xs)
if len(p) == 0:
print(s + " is the first ordering of its letters; nothing comes before it.")
else:
print("before " + s + ": " + word(p))
if len(n) == 0:
print(s + " is the last ordering of its letters; nothing comes after it.")
else:
print("after " + s + ": " + word(n))
def place():
s = ask_word("word with different letters (1 to 12)> ", 12, True)
if s == "":
print("Cancelled.")
return
xs = letters(s)
r = arrange.rank(xs)
total = arrange.factorial(len(xs))
print(s + " is number " + str(r) + " of the " + str(total) + " orderings of its letters, in dictionary order.")
back = arrange.unrank(xs, r)
print("Number " + str(r) + " read back the other way is " + word(back) + ".")
def at_place():
s = ask_word("letters, all different (1 to 12)> ", 12, True)
if s == "":
print("Cancelled.")
return
total = arrange.factorial(len(s))
k = ask("place", 1, total)
if k == -1:
print("Cancelled.")
return
w = arrange.unrank(letters(s), k)
print("Ordering number " + str(k) + " of " + word(arrange.sorted_copy(letters(s))) + " is " + word(w) + ".")
def choose():
s = ask_word("items, all different (1 to 10)> ", 10, True)
if s == "":
print("Cancelled.")
return
k = ask("how many to choose", 0, len(s))
if k == -1:
print("Cancelled.")
return
cs = arrange.combinations(letters(s), k, 0, [], [])
line = ""
i = 0
for c in cs:
if i < 30:
if line != "":
line = line + " "
if len(c) == 0:
line = line + "(none)"
else:
line = line + word(c)
i = i + 1
if len(cs) > 30:
line = line + " ... (" + str(len(cs) - 30) + " more)"
print(line)
w = "ways"
if len(cs) == 1:
w = "way"
print(str(len(cs)) + " " + w + " = " + str(len(s)) + "! / (" + str(k) + "! " + str(len(s) - k) + "!).")
def decimal(a, b, places):
s = "0."
r = a
for i in range(1, places+1):
r = r * 10
d = 0
while r >= b:
r = r - b
d = d + 1
s = s + str(d)
return s
def mixed_up():
n = ask("n", 1, 20)
if n == -1:
print("Cancelled.")
return
d = arrange.derangements(n)
f = arrange.factorial(n)
print("Of the " + str(f) + " orderings of " + str(n) + " things, " + str(d) + " leave none in its place.")
print("That is " + decimal(d, f, 12) + " of them; 1/e is 0.367879441171..., which the share closes in on as n grows.")
print("Each count is (n - 1) x (the two before added): the first thing goes to one of n - 1 places, and then it either swaps or does not.")
def gray_code():
s = ask_word("items for the subsets (1 to 5)> ", 5, True)
if s == "":
print("Cancelled.")
return
codes = arrange.gray(len(s))
for c in codes:
sub = ""
for i in range(0, len(s)):
if c[i] == "1":
sub = sub + s[i]
if sub == "":
sub = "(none)"
print(" " + c + " " + sub)
print("All " + str(len(codes)) + " subsets, each one item in or out from the one before - the Gray code.")
print("== Permutations and combinations ==")
print("Orderings, dictionary order, places, combinations, derangements and Gray codes.")
running = True
while running:
print("")
print("1) orderings 2) next and previous 3) place of an ordering 4) ordering at a place 5) combinations 6) derangements 7) Gray code 8) quit")
choice = trim(input("choice> "))
if choice == "1":
orderings()
elif choice == "2":
neighbours()
elif choice == "3":
place()
elif choice == "4":
at_place()
elif choice == "5":
choose()
elif choice == "6":
mixed_up()
elif choice == "7":
gray_code()
elif choice == "8":
running = False
else:
print("Pick a number from 1 to 8.")
print("Bye.")
arrange.eml
eml# P084 permutations and combinations - every ordering of a few items, the
# next one in dictionary order, an ordering's place in that order and the
# ordering at a given place, combinations, derangements and Gray codes.
# Items are lists of one-character strings.
def permute(items, current, used, out):
# The corpus case permutations-generator: pick an unused item, go on
# with the rest, then free it again for the next branch. `used` is
# changed in place, so it must be undone; `current` is a new list each
# time, so it need not be.
if len(current) == len(items):
return out + [current]
for i in [0:len(items) - 1]:
if used[i] == 0:
1 => used[i]
permute(items, current + [items[i]], used, out) => out
0 => used[i]
return out
def sorted_copy(xs):
[0] * len(xs) => out
for i in [0:len(xs) - 1]:
xs[i] => out[i]
for i in [1:len(out) - 1]:
out[i] => x
i - 1 => j
while j >= 0 and out[j] > x:
out[j] => out[j + 1]
j - 1 => j
x => out[j + 1]
return out
def distinct(items):
# Orderings with repeated items counted once: n! / (k1! k2! ...).
# Exact: the factorials divide.
sorted_copy(items) => s
factorial(len(s)) => total
0 => i
while i < len(s):
i => j
while j < len(s) and s[j] == s[i]:
j + 1 => j
divide(total, factorial(j - i)) => total
j => i
return total
def factorial(n):
1 => f
for k in [2:n]:
f * k => f
return f
def divide(a, b):
# a / b when b divides a, digit by digit (exact at any size).
0 => q
0 => r
for ch in str(a):
r * 10 + int(ch) => r
0 => d
while r >= b:
r - b => r
d + 1 => d
q * 10 + d => q
return q
def next_perm(xs):
# The next ordering in dictionary order, or [] after the last: find the
# rightmost place i with xs[i] < xs[i + 1], swap xs[i] with the
# rightmost item bigger than it, and reverse what follows i.
[0] * len(xs) => a
for k in [0:len(xs) - 1]:
xs[k] => a[k]
len(a) - 2 => i
while i >= 0 and a[i] >= a[i + 1]:
i - 1 => i
if i < 0:
return []
len(a) - 1 => j
while a[j] <= a[i]:
j - 1 => j
a[i] => t
a[j] => a[i]
t => a[j]
i + 1 => lo
len(a) - 1 => hi
while lo < hi:
a[lo] => t
a[hi] => a[lo]
t => a[hi]
lo + 1 => lo
hi - 1 => hi
return a
def prev_perm(xs):
# The ordering just before, or [] before the first: the same steps with
# every comparison turned round.
[0] * len(xs) => a
for k in [0:len(xs) - 1]:
xs[k] => a[k]
len(a) - 2 => i
while i >= 0 and a[i] <= a[i + 1]:
i - 1 => i
if i < 0:
return []
len(a) - 1 => j
while a[j] >= a[i]:
j - 1 => j
a[i] => t
a[j] => a[i]
t => a[j]
i + 1 => lo
len(a) - 1 => hi
while lo < hi:
a[lo] => t
a[hi] => a[lo]
t => a[hi]
lo + 1 => lo
hi - 1 => hi
return a
def rank(xs):
# The place (from 1) of an ordering of different items among all
# orderings of them in dictionary order: for each position, how many
# smaller items are still to come, times the orderings of the rest -
# the factorial number system.
0 => r
len(xs) => n
for i in [0:n - 1]:
0 => smaller
for j in [i + 1:n - 1]:
if xs[j] < xs[i]:
smaller + 1 => smaller
r + smaller * factorial(n - 1 - i) => r
return r + 1
def unrank(items, place):
# The ordering at `place` (from 1): the same digits read the other way.
sorted_copy(items) => left
place - 1 => r
[] => out
len(items) => n
for i in [0:n - 1]:
factorial(n - 1 - i) => f
0 => d
while r >= f:
r - f => r
d + 1 => d
out + [left[d]] => out
[] => rest
for k in [0:len(left) - 1]:
if k != d:
rest + [left[k]] => rest
rest => left
return out
def combinations(items, k, start, current, out):
# Every choice of k items, in the order the items come.
if len(current) == k:
return out + [current]
for i in [start:len(items) - 1]:
if len(items) - i >= k - len(current):
combinations(items, k, i + 1, current + [items[i]], out) => out
return out
def derangements(n):
# Orderings that leave no item in its place: D(n) = (n - 1)(D(n - 1) +
# D(n - 2)), D(0) = 1, D(1) = 0.
1 => a
0 => b
if n == 0:
return 1
for k in [2:n]:
(k - 1) * (a + b) => c
b => a
c => b
return b
def gray(n):
# The n-bit reflected Gray code: the (n - 1)-bit code, then the same
# reversed, with 0 and then 1 in front - one bit changes each step.
[""] => codes
for k in [1:n]:
[] => out
for c in codes:
out + ["0" + c] => out
len(codes) - 1 => i
while i >= 0:
out + ["1" + codes[i]] => out
i - 1 => i
out => codes
return codes
Python projection (arrange.py)
def permute(items, current, used, out):
if len(current) == len(items):
return out + [current]
for i in range(0, len(items)):
if used[i] == 0:
used[i] = 1
out = permute(items, current + [items[i]], used, out)
used[i] = 0
return out
def sorted_copy(xs):
out = [0] * len(xs)
for i in range(0, len(xs)):
out[i] = xs[i]
for i in range(1, len(out)):
x = out[i]
j = i - 1
while j >= 0 and out[j] > x:
out[j + 1] = out[j]
j = j - 1
out[j + 1] = x
return out
def distinct(items):
s = sorted_copy(items)
total = factorial(len(s))
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j = j + 1
total = divide(total, factorial(j - i))
i = j
return total
def factorial(n):
f = 1
for k in range(2, n+1):
f = f * k
return f
def divide(a, b):
q = 0
r = 0
for ch in str(a):
r = r * 10 + int(ch)
d = 0
while r >= b:
r = r - b
d = d + 1
q = q * 10 + d
return q
def next_perm(xs):
a = [0] * len(xs)
for k in range(0, len(xs)):
a[k] = xs[k]
i = len(a) - 2
while i >= 0 and a[i] >= a[i + 1]:
i = i - 1
if i < 0:
return []
j = len(a) - 1
while a[j] <= a[i]:
j = j - 1
t = a[i]
a[i] = a[j]
a[j] = t
lo = i + 1
hi = len(a) - 1
while lo < hi:
t = a[lo]
a[lo] = a[hi]
a[hi] = t
lo = lo + 1
hi = hi - 1
return a
def prev_perm(xs):
a = [0] * len(xs)
for k in range(0, len(xs)):
a[k] = xs[k]
i = len(a) - 2
while i >= 0 and a[i] <= a[i + 1]:
i = i - 1
if i < 0:
return []
j = len(a) - 1
while a[j] >= a[i]:
j = j - 1
t = a[i]
a[i] = a[j]
a[j] = t
lo = i + 1
hi = len(a) - 1
while lo < hi:
t = a[lo]
a[lo] = a[hi]
a[hi] = t
lo = lo + 1
hi = hi - 1
return a
def rank(xs):
r = 0
n = len(xs)
for i in range(0, n):
smaller = 0
for j in range(i + 1, n):
if xs[j] < xs[i]:
smaller = smaller + 1
r = r + smaller * factorial(n - 1 - i)
return r + 1
def unrank(items, place):
left = sorted_copy(items)
r = place - 1
out = []
n = len(items)
for i in range(0, n):
f = factorial(n - 1 - i)
d = 0
while r >= f:
r = r - f
d = d + 1
out = out + [left[d]]
rest = []
for k in range(0, len(left)):
if k != d:
rest = rest + [left[k]]
left = rest
return out
def combinations(items, k, start, current, out):
if len(current) == k:
return out + [current]
for i in range(start, len(items)):
if len(items) - i >= k - len(current):
out = combinations(items, k, i + 1, current + [items[i]], out)
return out
def derangements(n):
a = 1
b = 0
if n == 0:
return 1
for k in range(2, n+1):
c = (k - 1) * (a + b)
a = b
b = c
return b
def gray(n):
codes = [""]
for k in range(1, n+1):
out = []
for c in codes:
out = out + ["0" + c]
i = len(codes) - 1
while i >= 0:
out = out + ["1" + codes[i]]
i = i - 1
codes = out
return codes