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

All times are UTC + 1 hour




Post new topic Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Fast permutations...
PostPosted: Mon Dec 01, 2008 10:39 pm 
Offline
Addict
Addict
User avatar

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 :lol:

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
 Profile  
Reply with quote  
 Post subject:
PostPosted: Tue Dec 02, 2008 10:25 am 
Offline
Enthusiast
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
________
http://blog.forex-trading-ideas.com


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Tue Dec 02, 2008 1:59 pm 
Offline
Enthusiast
Enthusiast
User avatar

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
 Profile  
Reply with quote  
 Post subject:
PostPosted: Tue Dec 02, 2008 9:56 pm 
Offline
Addict
Addict
User avatar

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
 Profile  
Reply with quote  
 Post subject:
PostPosted: Tue Dec 02, 2008 10:51 pm 
Offline
Addict
Addict

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


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

Regards, Little John

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


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Tue Dec 02, 2008 10:58 pm 
Offline
Addict
Addict
User avatar

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.

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Tue Dec 02, 2008 11:10 pm 
Offline
Addict
Addict
User avatar

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 :oops:

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
 Profile  
Reply with quote  
 Post subject:
PostPosted: Tue Dec 02, 2008 11:36 pm 
Offline
Addict
Addict
User avatar

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

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Wed Dec 03, 2008 12:05 am 
Offline
Addict
Addict

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

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

k = 3
sum = 3

mini = 0
maxi = k

That means that code after the line
Quote:
;---------- Your example ----------

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
 Profile  
Reply with quote  
 Post subject:
PostPosted: Wed Dec 03, 2008 12:22 am 
Offline
Addict
Addict
User avatar

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

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

k = 3
sum = 3

mini = 0
maxi = k

That means that code after the line
Quote:
;---------- Your example ----------

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.

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Wed Dec 03, 2008 12:43 am 
Offline
Addict
Addict

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
 Profile  
Reply with quote  
 Post subject:
PostPosted: Wed Dec 03, 2008 9:00 am 
Offline
Addict
Addict
User avatar

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
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 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 forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye