From: Axel Etzold Date: 2008-07-01T23:57:02+09:00 Subject: Re: how to - quickly make permutations? -------- Original-Nachricht -------- > Datum: Tue, 1 Jul 2008 23:15:21 +0900 > Von: Max Williams > An: ruby-talk@ruby-lang.org > Betreff: Re: how to - quickly make permutations? Max, > Axel Etzold wrote: > > > what are you trying to do ? The number of subsets is enormous... maybe > > there's > > an easier way to achieve your goal. > > > > Best regards, > > > > Axel > > Maybe there is...it's a little program to help my wife out with a bit of > data processing. I have a bunch of columns (50ish) that each list a > group of people. The people overlap between columns and we want to look > at what happens to the total degree of overlap when groups of columns > are removed. So, i was going to try removing each column and calculate > the total overlap for each case. Then, remove every possible pair of > columns, recalculate for each case. Then, every possible trio of > columns, etc. And keep going until the number of subsets to test starts > to get impractical. Which might happen quite quickly as you suggest. > -- > Posted via http://www.ruby-forum.com/. an alternative approach is simulated annealing ... it makes use of "jumping" in a space of parameters, where the jumps are initially quite big, but get smaller as your solution gets better. In this way, in nature, liquids that get cooled to crystals achieve very low energy configurations if cooled slowly... There's an implementation for Ruby using GSL http://rb-gsl.rubyforge.org/siman.html In your case, you could use a vector of 50 entries for the columns, each entry determining whether that column is in your subset at hand or not. In addition to that, you need a function that measures the quality of your solution, i.e. calculates the overlap. As the value of the vector entries is changed by the Iterator function implemented in Ruby-gsl when it jumps in the configuration space, you could say, "column i is in my subset, if the entry is positive, and otherwise not", then calculate the overlap resulting from that collection of subsets using the Set class,say, and then decide whether a lot of overlap is good or bad for your solution. The number of solutions to check is certainly far smaller than iterating through all subsets... Best regards, Axel -- GMX startet ShortView.de. Hier findest Du Leute mit Deinen Interessen! Jetzt dabei sein: http://www.shortview.de/wasistshortview.php?mc=sv_ext_mf@gmx