combinations and permutations (and anagrams)
Posted: 09 Jul 2017, 15:37
Has anybody released any good functions for calculating the number of combinations/permutations for the following:
- combinations (without repetition)
- combinations with repetition
- permutations (without repetition)
- permutations with repetition
Or are there any relevant MSDN functions available?
I have written functions both to calculate the numbers (what I'm asking for), and to generate lists of combinations/permutations, however they are very complicated and dependent on other functions, so I would be interested in any alternative approaches. Thanks. (I will release them soon.)
==================================================
Some related links:
[started by wolf_II]
Permutations() - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=6&t=34230
Anagrams - AutoHotkey Community
https://autohotkey.com/boards/viewtopic ... 19&t=34240
[started by littlegandhi1199]
Anagram Solver by Littlegandhi1199 - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=5&t=34082
(Scrabble) Anagram Solver N/4-15 - AutoHotkey Community
https://autohotkey.com/boards/viewtopic ... 19&t=34285
==================================================
E.g.
'who's in the photo' (order doesn't matter)
combinations: 'aab' and 'baa' are equivalent
combinations with repetitions (10): aaa,aab,aac,abb,abc,acc,bbb,bbc,bcc,ccc
combinations with no repetitions (1): abc
'how are the people in the photo lined up' (order matters)
permutations: 'aab' and 'baa' are not equivalent
permutations with repetitions (27): aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc
permutations with no repetitions (6): abc,acb,bac,bca,cab,cba
I'm looking to get those numbers: 10, 1, 27, 6, I'm not concerned about generating the lists.
==================================================
Part of the difficulty with calculation, is that you quickly reach numbers above what AutoHotkey can handle. The formulas typically use factorial, for example, 20! can be handled by AutoHotkey, but not 21!. E.g. 5! = 5*4*3*2*1 = 120. So I've had to use workarounds, like listing the prime factors of two different numbers, and cancelling them out, before applying a calculation.
One reason you'd want to know the numbers, is to calculate how much space will be required to store the list.
==================================================
COMBINATIONS (WITHOUT REPETITION) (N CHOOSE K):
Excel: COMBIN(n,k)
when k <= n: n! / (k!(n-k)!)
when k > n: 0
e.g. Fact(3) / (Fact(3)*Fact(3-3)) = 1
COMBINATIONS WITH REPETITION:
Excel: COMBIN(n+k-1,k)
Excel: FACT(n+k-1) / (FACT(n-1)*FACT(k))
when applicable: (n+k-1)! / (k!(n-1)!)
e.g. Fact(3+3-1)/(Fact(3-1)*Fact(3)) = 10
PERMUTATIONS (WITHOUT REPETITION):
Excel: PERMUT(n,k)
when k <= n: n! / (n-k)!
when k > n: 0
e.g. Fact(3) / Fact(3-3) = 6
PERMUTATIONS WITH REPETITION:
Excel: k^n
when applicable: k^n
e.g. 3**3 = 27
- combinations (without repetition)
- combinations with repetition
- permutations (without repetition)
- permutations with repetition
Or are there any relevant MSDN functions available?
I have written functions both to calculate the numbers (what I'm asking for), and to generate lists of combinations/permutations, however they are very complicated and dependent on other functions, so I would be interested in any alternative approaches. Thanks. (I will release them soon.)
==================================================
Some related links:
[started by wolf_II]
Permutations() - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=6&t=34230
Anagrams - AutoHotkey Community
https://autohotkey.com/boards/viewtopic ... 19&t=34240
[started by littlegandhi1199]
Anagram Solver by Littlegandhi1199 - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=5&t=34082
(Scrabble) Anagram Solver N/4-15 - AutoHotkey Community
https://autohotkey.com/boards/viewtopic ... 19&t=34285
==================================================
E.g.
'who's in the photo' (order doesn't matter)
combinations: 'aab' and 'baa' are equivalent
combinations with repetitions (10): aaa,aab,aac,abb,abc,acc,bbb,bbc,bcc,ccc
combinations with no repetitions (1): abc
'how are the people in the photo lined up' (order matters)
permutations: 'aab' and 'baa' are not equivalent
permutations with repetitions (27): aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc
permutations with no repetitions (6): abc,acb,bac,bca,cab,cba
I'm looking to get those numbers: 10, 1, 27, 6, I'm not concerned about generating the lists.
==================================================
Part of the difficulty with calculation, is that you quickly reach numbers above what AutoHotkey can handle. The formulas typically use factorial, for example, 20! can be handled by AutoHotkey, but not 21!. E.g. 5! = 5*4*3*2*1 = 120. So I've had to use workarounds, like listing the prime factors of two different numbers, and cancelling them out, before applying a calculation.
One reason you'd want to know the numbers, is to calculate how much space will be required to store the list.
==================================================
COMBINATIONS (WITHOUT REPETITION) (N CHOOSE K):
Excel: COMBIN(n,k)
when k <= n: n! / (k!(n-k)!)
when k > n: 0
e.g. Fact(3) / (Fact(3)*Fact(3-3)) = 1
COMBINATIONS WITH REPETITION:
Excel: COMBIN(n+k-1,k)
Excel: FACT(n+k-1) / (FACT(n-1)*FACT(k))
when applicable: (n+k-1)! / (k!(n-1)!)
e.g. Fact(3+3-1)/(Fact(3-1)*Fact(3)) = 10
PERMUTATIONS (WITHOUT REPETITION):
Excel: PERMUT(n,k)
when k <= n: n! / (n-k)!
when k > n: 0
e.g. Fact(3) / Fact(3-3) = 6
PERMUTATIONS WITH REPETITION:
Excel: k^n
when applicable: k^n
e.g. 3**3 = 27