0

Let's say I have 3 identical arrays, each looks like this: [1,2,3,4].

By choosing a value from each array, I want to exhaust all combinations, so in this example, the desired result would be:

[1,2,3], [1,2,4], [1,3,4],[2,3,4]

Order doesnt matter. I'm currently iterating over every possibility, and that's waaaay too slow. I thought about first doing a check to make sure the iterator is greater than the one to the left of it, but in the case of 1,4,... that would fail because the 3rd array doesn't have anything bigger than 4. So additionally I'd need to do a check to make sure the max of each column is no greater than column length - (# of repeating columns - column position. For example column 2 could not exceed 3. But I think I'm going down the rabbit hole.

Any clever ways to get the desired result in the fewest iterations possible? Modifying the arrays is fair game, too.

Matt K
  • 4,813
  • 4
  • 22
  • 35
  • 1
    I'm thinking that if you described the actual problem you're trying to solve, we might be able to come up with a better way than generating all possible combinatorials. – jfriend00 Jul 05 '15 at 20:15
  • Is there any meaningful reason you need n (3) identical arrays? Is that somehow different than using a single array n times? – Amit Jul 05 '15 at 20:16
  • It's look like Cartesian product? )) – stdob-- Jul 05 '15 at 20:24
  • possible duplicate of [cartesian product of multiple arrays in javascript](http://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript) – stdob-- Jul 05 '15 at 20:28
  • Yeah, so real-world scenario it's like a modified branch and bound. The input is anywhere from 2 to 7 arrays and each array has a certain class. The solution can have 2 results from the same class. So, for example, lets say the optimal mix consists of a Class 2, a Class 3, and another Class 3. The Class 2 array has 50 possibilities, the Class 3 has 40 possibilities. Currently I check each combo: 50*40*40, but ideally I'd only check 50*780 (where 780 is 40 choose 2). Hope this clears it up! – Matt K Jul 05 '15 at 20:28
  • Stdob, yup! sorry I should've mentioned that, it is a Cartesian product I'm after, but the access pattern is a little different than anything I've been able to find. – Matt K Jul 05 '15 at 20:34
  • If I understand correctly, after computing the Cartesian product is necessary to remove those vectors that have the same values for the second and third part? – stdob-- Jul 05 '15 at 20:47
  • Nope, removal not necessary. Currently I just iterate through using an index counter (for 3 arrays with respective classes of 2,3,3 and lengths of 50,40,40 my index counter increments the last value first so if I increment [0,0,40] it becomes [0,1,0], kinda like an old alarm clock. I'm open to new methods if I could increase performance without a huge hit to the memory. – Matt K Jul 05 '15 at 22:33
  • Consider providing code you have currently. Also make sure you know how many results you actually going to compute - helpful to know if it is "slow" because your code is not optimal OR because there is just large number of results. – Alexei Levenkov Jul 06 '15 at 01:27

0 Answers0