Fast permutations...
- Michael Vogel
- Addict
- Posts: 2666
- Joined: Thu Feb 09, 2006 11:27 pm
- Contact:
Fast permutations...
Hm,
who is able to give me a hint how to get all combinations if all possible ciphers which results in a number with a fixed length and the sum of all used ciphers have also a fix value.
Complicate Maybe, but only because of my weird english knowledge
But an example will explain it - let's search all numbers of a length of 3 ciphers where the sum of its ciphers is 1:
001
010
100
And what would are all results for length=3 / sum=3?
003
012
021
030
102
111
120
201
210
300
(Hopefully I haven't forgot a solution)
I need all possibilities up to a length=a / sum=b where a=1..22 and b=1..a*9, so a fast program for each combination would be great...
Michael
who is able to give me a hint how to get all combinations if all possible ciphers which results in a number with a fixed length and the sum of all used ciphers have also a fix value.
Complicate Maybe, but only because of my weird english knowledge
But an example will explain it - let's search all numbers of a length of 3 ciphers where the sum of its ciphers is 1:
001
010
100
And what would are all results for length=3 / sum=3?
003
012
021
030
102
111
120
201
210
300
(Hopefully I haven't forgot a solution)
I need all possibilities up to a length=a / sum=b where a=1..22 and b=1..a*9, so a fast program for each combination would be great...
Michael
-
- Enthusiast
- Posts: 767
- Joined: Sat Jan 24, 2004 6:56 pm
Hi Michael,
even if I don't have a solution at hand, this problem is one that interests me a lot. I've done some internet searching and came up with a number of links that might interest you:
http://en.wikipedia.org/wiki/Permutation
http://www.themathpage.com/aprecalc/per ... ations.htm
http://hyperphysics.phy-astr.gsu.edu/hb ... ermut.html
even if I don't have a solution at hand, this problem is one that interests me a lot. I've done some internet searching and came up with a number of links that might interest you:
http://en.wikipedia.org/wiki/Permutation
http://www.themathpage.com/aprecalc/per ... ations.htm
http://hyperphysics.phy-astr.gsu.edu/hb ... ermut.html
hihi, currently at work here but i found this in Python on a quick dig:
maybe useful - should be easy enough to convert:
maybe useful - should be easy enough to convert:
Code: Select all
# a simple recursive permutation function
# the number of permutations of a sequence of n unique items is given by n! (n factorial)
# more details at http://mathworld.wolfram.com/Permutation.html
# tested with Python24 vegaseat 16feb2006
def permutate(seq):
"""permutate a sequence and return a list of the permutations"""
if not seq:
return [seq] # is an empty sequence
else:
temp = []
for k in range(len(seq)):
part = seq[:k] + seq[k+1:]
#print k, part # test
for m in permutate(part):
temp.append(seq[k:k+1] + m)
#print m, seq[k:k+1], temp # test
return temp
# test the module
if __name__ == "__main__":
# permutate a string, how many recognizable words does this generate?
print permutate('owl')
print permutate('art')
# test for duplicates
blist = permutate('bush')
print "items in bush list =", len(blist) # should be 4! or 1*2*3*4 = 24
print "items in bush set =", len(set(blist)) # should be the same
tlist = permutate('tart')
print "items in tart list =", len(tlist) # should be 4! or 1*2*3*4 = 24
print "items in tart set =", len(set(tlist)) # less unique since there are two 't'
# permutate a list
list1 = [7, 8, 9]
for list2 in permutate(list1):
print list2
"""
result =
['owl', 'olw', 'wol', 'wlo', 'low', 'lwo']
['art', 'atr', 'rat', 'rta', 'tar', 'tra']
items in bush list = 24
items in bush set = 24
items in tart list = 24
items in tart set = 12
[7, 8, 9]
[7, 9, 8]
[8, 7, 9]
[8, 9, 7]
[9, 7, 8]
[9, 8, 7]
"""
"In 3D there is never enough Time to do Things right,
but there's always enough Time to make them *look* right."
"psssst! i steal signatures... don't tell anyone! "
but there's always enough Time to make them *look* right."
"psssst! i steal signatures... don't tell anyone! "
- Michael Vogel
- Addict
- Posts: 2666
- Joined: Thu Feb 09, 2006 11:27 pm
- Contact:
Thanks for your help, the point for "my" problem is, how to filter from all permutations to certain results (sum of ciphers must be equal a certain value).
Without this reduction there would be a very long list of results (10^22 "permutations" for the maximum length of 22)...
Or, just with my given example for the lenght=3 and sum=3, there are already 4^3=64 possibilities for ciphers between 0 and 3, but only 10 of the numbers have the sum=3.
Without this reduction there would be a very long list of results (10^22 "permutations" for the maximum length of 22)...
Or, just with my given example for the lenght=3 and sum=3, there are already 4^3=64 possibilities for ciphers between 0 and 3, but only 10 of the numbers have the sum=3.
-
- Addict
- Posts: 4519
- Joined: Thu Jun 07, 2007 3:25 pm
- Location: Berlin, Germany
Michael,
permutations will not be of much help for you. You have to deal with ordered combinatons (= variations) with repetition.
Regards, Little John
permutations will not be of much help for you. You have to deal with ordered combinatons (= variations) with repetition.
I personally don't see any other way than getting all regarding variations with repetition, and then selecting the appropriate ones which give the desired sum. Yes, there can be a lot of cases, that's often a problem in combinatorics.Michael Vogel wrote:Thanks for your help, the point for "my" problem is, how to filter from all permutations to certain results (sum of ciphers must be equal a certain value).
Code: Select all
; PB 4.30 beta 5
EnableExplicit
Procedure.i next_variation_r (a(1), mini, maxi)
; Return the next variation with repetition on a()
; (in lexicographic order);
; ** In order to get all possible variations, a() must initially only
; contain 'mini' values. **
Protected i
i = ArraySize(a())
; carry if necessary
While a(i) >= maxi
a(i) = mini
i - 1
If i = 0
ProcedureReturn #False
EndIf
Wend
a(i) + 1
ProcedureReturn #True
EndProcedure
Procedure.q SumQ (a(1), start=0, last=-1)
Protected i, ret.q
If last = -1
last = ArraySize(a())
EndIf
ret = a(start)
For i = start+1 To last
ret + a(i)
Next
ProcedureReturn ret
EndProcedure
;---------- Utility function ----------
Procedure.s GetIntegerArray (a(1), start=0, last=-1)
Protected i, text.s
If last = -1
last = ArraySize(a())
EndIf
text = ""
For i = start To last
text + Str(a(i))
If i < last
text + ","
EndIf
Next
ProcedureReturn text
EndProcedure
;---------- Your example ----------
Define i, k, mini, maxi, sum, count
k = 3
sum = 3
mini = 0
maxi = k
Dim a(k)
For i = 1 To k
a(i) = mini
Next
count = 0
Repeat
If SumQ(a(), 1) = sum
count + 1
Debug Str(count) + ": {" + GetIntegerArray(a(), 1) + "}"
EndIf
Until next_variation_r(a(), mini, maxi) = #False
- Michael Vogel
- Addict
- Posts: 2666
- Joined: Thu Feb 09, 2006 11:27 pm
- Contact:
In my quick testing of the code Little John presented I discovered it does not use the range of digits allowed (i.e. 0 -> 9). It only uses digits that are less than or equal to the length of the variations (i.e 0 -> 4 for 4 digits, 0 -> 5 for 5 digits, etc.).Michael Vogel wrote:Made a quick check - works fine, now I'll try to understand the code - thanks again!
This can be corrected in the code by changing line#70 from
Code: Select all
maxi = k
Code: Select all
maxi = 9 ;largest digit to select from
If maxi > sum : maxi = sum: EndIf ;add this line to limit the range for small sums
-
- Addict
- Posts: 4519
- Joined: Thu Jun 07, 2007 3:25 pm
- Location: Berlin, Germany
That means that code after the lineMe wrote:;---------- Your example ----------
Define i, k, mini, maxi, sum, count
k = 3
sum = 3
mini = 0
maxi = k
just was referring to the example that Michael had posted earlier, where the values were in the range from 0 to k.;---------- Your example ----------
The reason why I did introduce the variables 'mini' and 'maxi' was exactly, that any desired values can be assigned to them.
Regards, Little John
@Little John:
I meant no offense, the clarification was for Michael.
It's minor but your example code implied a relationship between k and maxi that was contrary to the example being shown as well as the specifications that Michael had requested. It should have been coded asLittle John wrote:That means that code after the lineMe wrote:;---------- Your example ----------
Define i, k, mini, maxi, sum, count
k = 3
sum = 3
mini = 0
maxi = kjust was referring to the example that Michael had posted earlier, where the values were in the range from 0 to k.;---------- Your example ----------
The reason why I did introduce the variables 'mini' and 'maxi' was exactly, that any desired values can be assigned to them.
Code: Select all
maxi = 3
I meant no offense, the clarification was for Michael.
-
- Addict
- Posts: 4519
- Joined: Thu Jun 07, 2007 3:25 pm
- Location: Berlin, Germany
There's also some permutation code in that project Euler thread from last year you could take a look at. I remember you we on that (or was it your thread? )
Paul Dwyer
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein