Asp Forum - Recursions problem

james

10/20/2015 5:54:00 AM

I have a function which will generate all the possible combination of number of list
When the number is big such as 58 (combination '(1 2) 58) the function will be hang there because it need do (power 2 58) times which is very huge . Is there any way to improve this?

(defun combination (list number)
;number > 1
(if (= 1 number)
(mapcar (lambda (e) (list e)) list)
(mapcan (lambda (e) (mapcar (lambda(e2) (cons e e2) ) (combination list (1- number)))) list))))

CL-USER> (combination '(1 2) 1)
((1) (2))
CL-USER> (combination '(1 2) 2)
((1 1) (1 2) (2 1) (2 2))
CL-USER> (combination '(1 2) 3)
((1 1 1) (1 1 2) (1 2 1) (1 2 2) (2 1 1) (2 1 2) (2 2 1) (2 2 2))

8 Answers

Pascal J. Bourguignon

10/20/2015 7:09:00 AM

james <dinglei2008@gmail.com> writes:

> I have a function which will generate all the possible combination of
> number of list When the number is big such as 58 (combination '(1 2)
> 58) the function will be hang there because it need do (power 2 58)
> times which is very huge . Is there any way to improve this?

Yes. Fork 2^58 parallel universes, have each of them return a single
permutation and collect them.

Now, to store the permutations, you will need about a exabyte of memory.
(ceiling (log (expt 2 58) 10)) -> 18.
If you store that on 4TB hard disks @ 140 euro each,
(* (/ 1e18 4e12) 140) -> 35,000,000.00 euro
you will need only 35 million euro, this remains quite accessible, even
factoring in the hardware required to drive it and the parallel universe
interface, which, you are lucky, is about to be developped at the CERN.

http://www.express.co.uk/news/world/565315/Scientists-at-Large-Hadron-Collider-hope-to-make-contact-with-PARALLEL-UNIVER...

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Jim Newton

10/20/2015 7:32:00 AM

Hi James, some time back, I wrote an article about this, albeit for a different lisp dialect. You might find it interesting.

One of the ideas was not to generate the list of permutations, but pass a visitor function and apply that function to the permutations, until you find the one which does the trick. I.e., you probably really don't want all the permutations, but you want to find a permutation which has a certain property. Keep in mind that it will still take longer than the age of the universe to search ALL the permutations of a moderate length list.

Enjoy the article, I hope it helps.

http://community.cadence.com/cadence_blogs_8/b/cic/archive/2013/09/05/skill-for-the-skilled-visiting-all-pe...

Jim Newton

10/20/2015 7:36:00 AM

Hi Pascal, the fact that it is impossible to generate all permutations does not stop people from trying to do it.

Jim Newton

10/20/2015 7:38:00 AM

A funny comment on algorithm E (Ehrlich swaps) from Donald E. Knuth, The Art of Computer Programming Volume 4 Fascicle 2, Generating All Tuples and Permutations, page 57.

According to Gideon Ehrlich, the original author of this algorithm, the most amazing thing about it is that it works.

james

10/22/2015 6:22:00 AM

On Tuesday, October 20, 2015 at 3:09:23 PM UTC+8, informatimago wrote:
> james <dinglei2008@gmail.com> writes:
>
> > I have a function which will generate all the possible combination of
> > number of list When the number is big such as 58 (combination '(1 2)
> > 58) the function will be hang there because it need do (power 2 58)
> > times which is very huge . Is there any way to improve this?
>
> Yes. Fork 2^58 parallel universes, have each of them return a single
> permutation and collect them.
>
> Now, to store the permutations, you will need about a exabyte of memory.
> (ceiling (log (expt 2 58) 10)) -> 18.
> If you store that on 4TB hard disks @ 140 euro each,
> (* (/ 1e18 4e12) 140) -> 35,000,000.00 euro
> you will need only 35 million euro, this remains quite accessible, even
> factoring in the hardware required to drive it and the parallel universe
> interface, which, you are lucky, is about to be developped at the CERN.
>
> http://www.express.co.uk/news/world/565315/Scientists-at-Large-Hadron-Collider-hope-to-make-contact-with-PARALLEL-UNIVER...
>
> --
> __Pascal Bourguignon__ http://www.informat...
> "The factory of the future will have only two employees, a man and a
> dog. The man will be there to feed the dog. The dog will be there to
> keep the man from touching the equipment." -- Carl Bass CEO Autodesk

Wow, I think I don't need to store result but just iterate them.

james

10/22/2015 6:24:00 AM

On Tuesday, October 20, 2015 at 3:31:51 PM UTC+8, Jim Newton wrote:
> Hi James, some time back, I wrote an article about this, albeit for a different lisp dialect. You might find it interesting.
>
> One of the ideas was not to generate the list of permutations, but pass a visitor function and apply that function to the permutations, until you find the one which does the trick. I.e., you probably really don't want all the permutations, but you want to find a permutation which has a certain property. Keep in mind that it will still take longer than the age of the universe to search ALL the permutations of a moderate length list.
>
> Enjoy the article, I hope it helps.
>
> http://community.cadence.com/cadence_blogs_8/b/cic/archive/2013/09/05/skill-for-the-skilled-visiting-all-pe...

Thanks to point this which bring me a new sight.

William James

10/22/2015 6:55:00 AM

james wrote:

> > james <dinglei2008@gmail.com> writes:
> >
> > > I have a function which will generate all the possible combination of
> > > number of list When the number is big such as 58 (combination '(1 2)
> > > 58) the function will be hang there because it need do (power 2 58)
> > > times which is very huge . Is there any way to improve this?
....
>
> Wow, I think I don't need to store result but just iterate them.

If you do 1,000,000 per second, it will take you about 9133 years.

Do you think that you have that long?

You are obviously the ieal worshipper of CL (COBOL-Like).

William James

10/22/2015 6:58:00 AM

WJ wrote:

> james wrote:
>
> > > james <dinglei2008@gmail.com> writes:
> > >
> > > > I have a function which will generate all the possible combination of
> > > > number of list When the number is big such as 58 (combination '(1 2)
> > > > 58) the function will be hang there because it need do (power 2 58)
> > > > times which is very huge . Is there any way to improve this?
> ....
> >
> > Wow, I think I don't need to store result but just iterate them.
>
> If you do 1,000,000 per second, it will take you about 9133 years.
>
> Do you think that you have that long?
>
> You are obviously the ieal worshipper of CL (COBOL-Like).
^^^^
ideal

comp.lang.lisp

Recursions problem

james

Pascal J. Bourguignon

Jim Newton

Jim Newton

Jim Newton

james

james

William James

William James

x Login to ForumsZone