C++ Find all combinations of elements in multiple arrays in Breadth-first search manner
<p>I've got multiple arrays and want to find the permutations of all the elements in these arrays. Each element also carries a weight, and these arrays are sorted decreasing by weight. I've got an array with weight that mimics the arrays with he values themselves. I want my search to find permutations with the greatest weight to the lowest weight.</p>

<p>However, each element in an array has a weight associated with it so I want to run my search with those with the highest weight first.</p>

<p>Example:  </p>

<pre><code>arr0 = [A, B, C, D]  
arr0_weight = [11, 7, 4, 3]  
arr1 = [W, X, Y]  
arr1_weight = [10, 9, 4]  
</code></pre>

<p>Thus, the ideal output would be:  </p>

<pre><code>AW (11+10=21)  
AX (11+9=20)  
BW (7+10=17)  
BX (7+9=16)  
AY (11+4=15)  
...  
</code></pre>

<p>If I did just a for loop like this:  </p>

<pre><code>for (int i = 0; i &lt; sizeof(arr0)/4; i++) {
  for (int j = 0; j &lt; sizeof(arr1)/4; j++) {
    cout &lt;&lt; arr0[i] &lt;&lt; arr1[j] &lt;&lt; endl; }}  
</code></pre>

<p>I would get: </p>

<pre><code>AW (11+10=21)   
AX (11+9=20)  
AY (11+4=15)  
BW (7+10=17)  
BX (7+9=16)  
BZ (7+4=11)  
</code></pre>

<p>Which isn't what I want because 17 > 15 and 16 > 15. </p>

<p>Also, what's a good way to do this for n arrays? If I don't know how many arrays I will have, and their size might not all be the same?</p>

<p>I've looked into putting the values into vectors but I can't find a way to do what I want (a sorted Cartesian product). Any help? Pseudo-code is fine if you don't have time - I'm just really stuck.</p>

<p>Thanks so much. </p>