Re: (Golf challenge) (to cover my embarassment!)

Produce a function that: passed two arrays (or array refs) returns an AoA containing all possible sequences of the two input arrays according to the "random pick - values in sequence" specified in the OP.

Rules: Strict + warnings. Array contents can be anything.

Entries that take longer than an hour to run for input arrays of ~~100~~ 10 elements (184756 sequences) each are disqualified:)

See thospel's post for the reason for the rule change. It's still an interesting problem to solve, even without golfing it.

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Comment on Re: (Golf challenge) (to cover my embarassment!)

Replies are listed 'Best First'.
Re^2: (Golf challenge) (to cover my embarassment!) by thospel (Hermit) on Oct 02, 2004 at 17:07 UTC
There will be C(m+n,n) solutions, so for two 100 element input arrays that's 9e58 solutions, to be generated in one hour. I think I need to upgrade my computer.	[reply]
Re^3: (Golf challenge) (to cover my embarassment!) by BrowserUk (Patriarch) on Oct 02, 2004 at 17:21 UTC
Geez! I knew it was getting big pretty quickly but I only needed to know up as far as 7x7 (3432) so I didn't generate it any further. I had no idea that it would get that big. Thanks for the formula.	[reply]
Several simple (simplistic?) notes by gaal (Parson) on Oct 02, 2004 at 06:57 UTC
First, for the original problem, there's the trivial solution of `(@t1, @t2)` because "fairness is not a consideration". More seriously, if we add the contraint of both lists having the same size in the second problem, all we need to do is to enumerate all binary numbers from zero to `2 size of one of the lists`. A zero numeral means take from t1, a one means take from t2. This is pretty fast. ~~Now to extend it for differently sized lists, you can just do the same but kill disqualifying members later. Probably no longer fastest, but the code would be golf fodder.~~ Update:** That's all wrong, as BrowserUk points out.	[reply] [d/l] [select]
Re: Several simple (simplistic?) notes by BrowserUk (Patriarch) on Oct 02, 2004 at 08:03 UTC
First, for the original problem, there's the trivial solution of (@t1, @t2) because "fairness is not a consideration". Nice:) Of course, generally speaking random implies unpredictable. The fairness bit was to indicate that not all possible sequences need have the same chance of being produced--but it should at least be possible that every sequence could be produced. enumerate all binary numbers from zero to 2 * size of one of the lists* I'm not sure I understand this? If we start with the trivial case of 2 lists of 2 elements. 2**2 = 4; enumerate the binary digits from 0 .. 4 gives: `000 001 010 011 100` [download] Five numbers; 15 digits; 5 '1's and 10 '0's. I can't see how that helps to produce the 6 sequences? `P:\test>395791 -N=2 1 2 a b 1 a 2 b 1 a b 2 a 1 2 b a 1 b 2 a b 1 2 6` [download] Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "Think for yourself!" - Abigail "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon	[reply] [d/l] [select]
Re^2: Several simple (simplistic?) notes by gaal (Parson) on Oct 02, 2004 at 08:54 UTC
Ah, right, that was a bad idea. I really meant `0 .. (2 ** (size * 2) - 1)`, but then there are many, many false candidates, and even too many good ones. For two lists of a hundred elements, we'd have to iterate over 2 ** 200 elements, which is a little too much :) /me goes off to try something else	[reply] [d/l]