Fast permutations...

Just starting out? Need help? Post your questions and find answers here.
User avatar
Michael Vogel
Addict
Addict
Posts: 2666
Joined: Thu Feb 09, 2006 11:27 pm
Contact:

Fast permutations...

Post by Michael Vogel »

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

Post by dell_jockey »

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
Thalius
Enthusiast
Enthusiast
Posts: 711
Joined: Thu Jul 17, 2003 4:15 pm
Contact:

Post by Thalius »

hihi, currently at work here but i found this in Python on a quick dig:
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! ;)"
User avatar
Michael Vogel
Addict
Addict
Posts: 2666
Joined: Thu Feb 09, 2006 11:27 pm
Contact:

Post by Michael Vogel »

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.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Post by Little John »

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: 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
Regards, Little John
User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Post by Demivec »

@Michael Vogel: I agree with Little John, you would need to find the combinations that match the sum, then find the permutations of those.
User avatar
Michael Vogel
Addict
Addict
Posts: 2666
Joined: Thu Feb 09, 2006 11:27 pm
Contact:

Post by Michael Vogel »

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!
User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Post by Demivec »

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: Select all

maxi = k
to:

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
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Post by Little John »

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
;---------- 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
User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Post by Demivec »

@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
;---------- 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: Select all

maxi = 3


I meant no offense, the clarification was for Michael.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Post by Little John »

No, my example code wasn't contrary to Michael's example.

EOD.
User avatar
pdwyer
Addict
Addict
Posts: 2813
Joined: Tue May 08, 2007 1:27 pm
Location: Chiba, Japan

Post by pdwyer »

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
Post Reply