# PureBasic Forum

 It is currently Sun Jan 24, 2021 3:38 am

 All times are UTC + 1 hour

 Page 1 of 1 [ 12 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Fast permutations...Posted: Mon Dec 01, 2008 10:39 pm

Joined: Thu Feb 09, 2006 11:27 pm
Posts: 2562
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

Top

 Post subject: Posted: Tue Dec 02, 2008 10:25 am
 Enthusiast

Joined: Sat Jan 24, 2004 6:56 pm
Posts: 768
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

_________________
cheers,
dell_jockey
________

Top

 Post subject: Posted: Tue Dec 02, 2008 1:59 pm
 Enthusiast

Joined: Thu Jul 17, 2003 4:15 pm
Posts: 711
hihi, currently at work here but i found this in Python on a quick dig:
maybe useful - should be easy enough to convert:
Code:
# 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! "

Top

 Post subject: Posted: Tue Dec 02, 2008 9:56 pm

Joined: Thu Feb 09, 2006 11:27 pm
Posts: 2562
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.

Top

 Post subject: Posted: Tue Dec 02, 2008 10:51 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3967
Location: Berlin, Germany
Michael,

permutations will not be of much help for you. You have to deal with ordered combinatons (= variations) with repetition.

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).

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.

Code:
; 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

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

Regards, Little John

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Posted: Tue Dec 02, 2008 10:58 pm

Joined: Mon Jul 25, 2005 3:51 pm
Posts: 3767
Location: Utah, USA
@Michael Vogel: I agree with Little John, you would need to find the combinations that match the sum, then find the permutations of those.

_________________

Top

 Post subject: Posted: Tue Dec 02, 2008 11:10 pm

Joined: Thu Feb 09, 2006 11:27 pm
Posts: 2562
Thanks, Little John and Demivec!

Sorry for using permutation instead of variation - created some confusion

But now I have to check the code of Little John!
Michael

Made a quick check - works fine, now I'll try to understand the code - thanks again!

Top

 Post subject: Posted: Tue Dec 02, 2008 11:36 pm

Joined: Mon Jul 25, 2005 3:51 pm
Posts: 3767
Location: Utah, USA
Michael Vogel wrote:
Made a quick check - works fine, now I'll try to understand the code - thanks again!

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.).

This can be corrected in the code by changing line#70 from
Code:
maxi = k

to:
Code:
maxi = 9 ;largest digit to select from
If maxi > sum : maxi = sum: EndIf ;add this line to limit the range for small sums

_________________

Top

 Post subject: Posted: Wed Dec 03, 2008 12:05 am

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3967
Location: Berlin, Germany
Me wrote:

Define i, k, mini, maxi, sum, count

k = 3
sum = 3

mini = 0
maxi = k

That means that code after the line
Quote:

just was referring to the example that Michael had posted earlier, where the values were in the range from 0 to k.
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

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Posted: Wed Dec 03, 2008 12:22 am

Joined: Mon Jul 25, 2005 3:51 pm
Posts: 3767
Location: Utah, USA
@Little John:
Little John wrote:
Me wrote:

Define i, k, mini, maxi, sum, count

k = 3
sum = 3

mini = 0
maxi = k

That means that code after the line
Quote:

just was referring to the example that Michael had posted earlier, where the values were in the range from 0 to k.
The reason why I did introduce the variables 'mini' and 'maxi' was exactly, that any desired values can be assigned to them.

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 as
Code:
maxi = 3

I meant no offense, the clarification was for Michael.

_________________

Top

 Post subject: Posted: Wed Dec 03, 2008 12:43 am

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3967
Location: Berlin, Germany
No, my example code wasn't contrary to Michael's example.

EOD.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Posted: Wed Dec 03, 2008 9:00 am

Joined: Tue May 08, 2007 1:27 pm
Posts: 2756
Location: Chiba, Japan
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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 12 posts ]

 All times are UTC + 1 hour

#### Who is online

Users browsing this forum: No registered users and 17 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - IDE    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite