Author Topic: -={ Challenge }=- Get Permutations  (Read 6255 times)

0 Members and 1 Guest are viewing this topic.

ribarm

  • Water Moccasin
  • Posts: 2357
  • Marko Ribar, architect
Re: -={ Challenge }=- Get Permutations
« Reply #15 on: February 23, 2013, 02:50:38 AM »
I don't have any math book, so just wondering, is there formula to get number of permutations - not to evaluate them all, just to find out the number?
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2357
  • Marko Ribar, architect
Re: -={ Challenge }=- Get Permutations
« Reply #16 on: February 23, 2013, 04:29:20 AM »
I answered my question :

n!

Code - Auto/Visual Lisp: [Select]
  1. ;;; N! ;;;
  2. ;;; number of Permutations wihout repetition of elements ;;;
  3. (defun nP ( n )
  4.   (if (> n 1) (* n (nP (1- n))) 1)
  5. )
  6.  
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: -={ Challenge }=- Get Permutations
« Reply #17 on: February 23, 2013, 11:25:10 AM »
I thought a permutation set was based on  ALL items in the base set and produced sets based on the item index in the original list rather than the uniqueness of the item. ... but I could be wrong.

Code - Python: [Select]
  1. import itertools
  2. set_size = 4
  3. data_set = (108, 99, 112, 118, 100, 102, 96, 101)
  4.  
  5. result = list(itertools.permutations(data_set, set_size))

result will be 1680 set lists based on the data-set
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: -={ Challenge }=- Get Permutations
« Reply #18 on: February 23, 2013, 11:31:40 AM »

So the original post problem result would be  :

Code - Python: [Select]
  1. result = list(itertools.permutations(('a', 'b', 'c')))
  2. for d in result:
  3.     print d

Code - Text: [Select]
  1. ('a', 'b', 'c')
  2. ('a', 'c', 'b')
  3. ('b', 'a', 'c')
  4. ('b', 'c', 'a')
  5. ('c', 'a', 'b')
  6. ('c', 'b', 'a')
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

Lee Mac

  • Seagull
  • Posts: 12379
  • London, England
Re: -={ Challenge }=- Get Permutations
« Reply #19 on: February 23, 2013, 11:49:21 AM »
I thought a permutation set was based on  ALL items in the base set and produced sets based on the item index in the original list rather than the uniqueness of the item. ... but I could be wrong.

Code - Python: [Select]
  1. import itertools
  2. set_size = 4
  3. data_set = (108, 99, 112, 118, 100, 102, 96, 101)
  4.  
  5. result = list(itertools.permutations(data_set, set_size))

result will be 1680 set lists based on the data-set

I'm not sure which post you are responding to, but my earlier post was in response to Irneb's specific request for a function to return a list of lists where the items in the source set may be used more than once, e.g.:

Code - Auto/Visual Lisp: [Select]
  1. _$ (nPr '(0 1) 2)
  2. ((0 0) (0 1) (1 0) (1 1))

Here, for k items chosen from a set of n items, this will produce a list of length kn

For your example where items in the source list are used only once, the function could be written:

Code - Auto/Visual Lisp: [Select]
  1. (defun nPr ( l r )
  2.    (if (< r 2)
  3.        (mapcar 'list l)
  4.        (apply 'append (mapcar '(lambda ( a ) (mapcar '(lambda ( b ) (cons a b)) (nPr (vl-remove a l) (1- r)))) l))
  5.    )
  6. )

Code - Auto/Visual Lisp: [Select]
  1. _$ (nPr '(0 1) 2)
  2. ((0 1) (1 0))

Now, for k items selected from a set of n items, this will produce a list of length n!/(n-k)!
Hence for your example of selecting 4 items from a list of 8 items, you would receive a list of 8!/4! = 1680

Or have I misunderstood your post?
« Last Edit: February 23, 2013, 12:09:27 PM by Lee Mac »

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: -={ Challenge }=- Get Permutations
« Reply #20 on: February 23, 2013, 11:54:54 AM »

Now, for k items selected from a set of n items, this will produce a list of length n!/k!
Hence for your example of selected 4 items from a list of 8 items, you would receive a list of 8!/4! = 1680

Or have I misread your post?

Exactly.

It's a great tool for solving anagrams.

added:
Sorry about introducing python into the mix ... it's what my head is full of this month. :)
.. at least it has lambda and map functionality ..
« Last Edit: February 23, 2013, 11:59:55 AM by Kerry »
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

Lee Mac

  • Seagull
  • Posts: 12379
  • London, England
Re: -={ Challenge }=- Get Permutations
« Reply #21 on: February 23, 2013, 12:03:27 PM »
Sorry I was mistaken, the number of permutations is n!/(n-k)!, not n!/k!
Then for combinations you have n!/[k!(n-k)!]

It's a great tool for solving anagrams.

:-D

« Last Edit: February 23, 2013, 12:08:52 PM by Lee Mac »

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: -={ Challenge }=- Get Permutations
« Reply #22 on: February 23, 2013, 12:58:47 PM »
Lee,
I agree with
 n! for full permutations
ie
n = 3 ; result is 6 sets
n = 5 ; results in 120 sets

and
 n!/(n-k)! for a divided set
ie
n = 8, k = 4 ; results in 1680 sets.
n = 8, k = 2 ; results in 56 sets

But I can't place your last calc  n!/[k!(n-k)!]   in the scheme of things. ( what you call combinations)
using n = 8, k=4 result would be 70 sets
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

Lee Mac

  • Seagull
  • Posts: 12379
  • London, England
Re: -={ Challenge }=- Get Permutations
« Reply #23 on: February 23, 2013, 01:10:57 PM »
But I can't place your last calc  n!/[k!(n-k)!]   in the scheme of things. ( what you call combinations)
using n = 8, k=4 result would be 70 sets

My understanding was that combinations differ from permutations in that the order of the elements in each subset does not matter for combinations.

Example: choose 2 items from (A B C):

Permutations [n!/(n-k)!] = 3!/1! = 6
Code: [Select]
((A B) (A C) (B A) (B C) (C A) (C B))
Combinations [n!/k!(n-k)!] = 3!/(2!1!) = 3
Code: [Select]
((A B) (A C) (B C))Hence where combinations are concerned, the subset (A B) == (B A), whereas these are distinct permutations.

Related thread on combinations:
www.theswamp.org/index.php?topic=2694

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: -={ Challenge }=- Get Permutations
« Reply #24 on: February 23, 2013, 01:40:05 PM »
OK, I had a fixation on permutations :)


This would do combinations for me this week

Code - Python: [Select]
  1. import itertools
  2. set_size = 2
  3. data_set = [ 'a', 'b', 'c' ]
  4. result = list(itertools.combinations(data_set, set_size))
  5. for d in result:
  6.     print d

Code - Text: [Select]
  1. ('a', 'b')
  2. ('a', 'c')
  3. ('b', 'c')

interesting discussion.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

Lee Mac

  • Seagull
  • Posts: 12379
  • London, England
Re: -={ Challenge }=- Get Permutations
« Reply #25 on: February 23, 2013, 01:53:35 PM »
This would do combinations for me this week
Code - Python: [Select]
  1. import itertools
  2. set_size = 2
  3. data_set = [ 'a', 'b', 'c' ]
  4. result = list(itertools.combinations(data_set, set_size))
  5. for d in result:
  6.     print d

Python certainly reduces the amount of work & code!

interesting discussion.

Definitely :-)

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: -={ Challenge }=- Get Permutations
« Reply #26 on: February 23, 2013, 01:59:39 PM »

Quote
Python certainly reduces the amount of work & code!

It does have some excellent libraries :)

The equivalent code in raw python instead of using the c++ library would be something like :
Code - Python: [Select]
  1. def combinations(iterable, r):
  2.     # combinations('ABCD', 2) --> AB AC AD BC BD CD
  3.     # combinations(range(4), 3) --> 012 013 023 123
  4.     pool = tuple(iterable)
  5.     n = len(pool)
  6.     if r > n:
  7.         return
  8.     indices = range(r)
  9.     yield tuple(pool[i] for i in indices)
  10.     while True:
  11.         for i in reversed(range(r)):
  12.             if indices[i] != i + n - r:
  13.                 break
  14.         else:
  15.             return
  16.         indices[i] += 1
  17.         for j in range(i+1, r):
  18.             indices[j] = indices[j-1] + 1
  19.         yield tuple(pool[i] for i in indices)

I posted that simply because I know you'll enjoy it :)


Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

Lee Mac

  • Seagull
  • Posts: 12379
  • London, England
Re: -={ Challenge }=- Get Permutations
« Reply #27 on: February 23, 2013, 06:51:53 PM »
The whole itertools library is huge!
There's some great inspiration for future AutoLISP challenges  :evil:

I guess my earlier function written for Irneb is the equivalent to the product Iterator.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: -={ Challenge }=- Get Permutations
« Reply #28 on: February 23, 2013, 07:38:51 PM »

It makes a difference when you CAN name your algorithm :)
.. rather than just have a description for it.


Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

Gasty

  • Newt
  • Posts: 90
Re: -={ Challenge }=- Get Permutations
« Reply #29 on: February 24, 2013, 03:51:50 PM »
Hi,

There is a very neat way to obtain the k-th permutation or combination in a lexicographic order, so you can pick exactly the item you want, without calculating all the data. The following piece of code use the factoradic and combinadic aproach to do that. Be careful as has very minimal error checking, and sure there is a lot to optimize.


A little explanation here:http://irenes-coding-blog.blogspot.com/2012/07/factorial-base-numbers-and-permutations.html
Code: [Select]

;;Example of using factoradics and combinadics to obtain the list of combinations and permutations in lexicographic order
;;Based on an article of Dr. James McCaffrey in MSDN Magazine
;;Gaston Nunez


;This will get the k-th element of a combination of k items over n    
(defun Element(n k m / ans a b x y i)
  (setq ans (vlax-make-safearray vlax-vbInteger (cons 0 (- k 1))))
  (setq a n)
  (setq b k)
  (setq x (dual m n k))
  (setq i 0)
  (while (< i k)
    (setq y (vlax-safearray-put-element ans i (largestV a b x)))
    (setq x (- x (Choose y b)))
    (setq a y)
    (setq b (- b 1))
    (setq i (+ i 1))
  )
  (setq i 0)
  (while (< i k)
    (setq z (- (- n 1)(vlax-safearray-get-element ans i)))
    (vlax-safearray-put-element ans i z)
    (setq i (+ i 1))
  ) 
  (vlax-safearray->list ans)
)

(defun dual(m n k)
 (- (- (choose n k) 1) m)
)

(defun LargestV(n k m / v)
  (setq v (- n 1))
  (while (> (Choose v k) m)
    (setq v (- v 1))
  )
  v
)

 ;;Calculate  n over k without explicit calling to factorials   
(defun Choose(n k / delta iMax i)
  (cond ((< n k) (setq ret 0))
((= n k) (setq ret 1))
((> n k)
        (if (< k (- n k))
  (progn
    (setq delta (- n k))
    (setq iMax k)
  )
  (progn
    (setq delta k)
    (setq iMax (- n k))
  )
)
(setq ret (+ delta 1))
(setq i 2)
(while (<= i iMax)
  (setq ret (/ (* ret (+ delta i)) i))
  (setq i (+ i 1))
)))
  ret
)



;;get de factoradic decomposition of a number k for groups of n elements
(defun getfactors(order k / j n factors m)
  (setq factors  (vlax-make-safearray vlax-vbInteger (cons 0 (- order 1))))
  (setq m (- order 1))
  (setq j 1)
  (setq n k)
  (while (<= j order)
    (vlax-safearray-put-element factors (- order j) (rem n j))
    (setq n (/ n j))
    (setq j (+ j 1))
  )
 (vlax-safearray->list factors)



;;Get the kth-permutation for a list of integer of length order
(defun get_nth_permut(order k / base i factors permuts index val)
  (setq base '())
  (setq i 0)
  (while (<= i (- order 1))
    (setq base (cons i base))
    (setq i (+ i 1))
  )
  (setq base (reverse base))
  (setq factors (getfactors order k))
  (setq permuts '())
  (setq i 0)
  (while (< i order)
    (setq index (nth i factors))
    (setq val (nth index base))
    (setq permuts (cons val permuts))
    (setq base (vl-remove val base))
    (setq i (+ i 1))
  )
  (reverse permuts)



(defun fact(n / ret i)
  (setq ret 1)
  (if (= n 0) ret
    (progn
      (setq i n)
      (while (>= i 1)
(setq ret (* ret i))
(setq i (- i 1))
      )
     )
   )
  ret
)


;;List all the permutations of a given list of integers, tipically (0 1 2 3...)
(defun ListPermutations(order / nperm i)
  (setq nperm (fact order))
  (setq i 0)
  (while (< i nperm)
    (print (get_nth_permut order i))
    (setq i (+ i 1))
  )
  (princ)

   

List all the combinations n over k of a list of integer (0 1 2 ...) in goups of k elements
(defun ListCombinations(n k / l i)
  (setq l (choose n k))
  (setq i 0)
  (while (< i l)
    (print (element n k i))
    (setq i (+ i 1))
  )
 (princ)
)


;;An example of how to obtain all the strings combinations for a string list.
(defun ListStringComb(strList k / n m i indexlist)
 (setq n (length strList))
 (setq m (choose n k))
 (setq i 0)
 (while (< i m)
   (setq indexList (element n k i))
   (print (getStrList indexList strList))
   (setq i (+ i 1))
 )
(princ)
)

(defun getStrList(indexlist strlist / x ret)
  (setq ret '())
  (foreach x indexlist
    (setq ret (cons (nth x strlist) ret))
  )
  (reverse ret)


Gaston Nunez