0

I have an array that looks like this: $arr_in = [0, 1, 2, 3, 4, 5, ...]

I need a function that will give me an array like this:

[
[[0, 1, 2, 3, 4, 5]],   
[[0, 4, 2, 3, 1, 5]],  
...
[[0, 1, 2, 3, 4], [ 5 ]], 
[[0, 1, 2, 3], [ 4, 5 ]], 
[[0, 1, 2], [ 3, 4, 5 ]],
[[0, 4, 2, 3, 1], [ 5 ]], 
[[0, 4, 2, 3], [ 1, 5 ]], 
[[0, 4, 2], [ 3, 1, 5 ]], 
...
[[0, 1, 2], [ 3, 4 ], [ 5 ]], 
...
[[0, 4, 2], [ 3, 1 ], [ 5 ]],
...
[[ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ]]
]

The order of the elements inside the subsets counts. (permutation)
[ [ 0, 1, 2, 3 ] [ 4, 5 ] ] and [ [ 1, 2, 3, 0 ] [ 4, 5 ] ] are 2 different sets.

The order of the subsets does not count. (combination)
[ [ 0, 1, 2, 3 ] [ 4, 5 ] ] and [ [ 4, 5 ] [ 0, 1, 2, 3 ] ] are the same set.

In the last line every element should be alone in its own sub-array.

Also the function needs to have a $level_min and $level_max where I can set the minimum and maximum of subsets inside the sets.

my_function( $arr_in, 2, 3 ) should only include sets of 2 and 3 subsets, like so:

[ 
[[0, 1, 2, 3, 4], [ 5 ]], 
[[0, 1, 2, 3], [ 4, 5 ]], 
[[0, 1, 2], [ 3, 4, 5 ]],
[[0, 4, 2, 3, 1], [ 5 ]], 
[[0, 4, 2, 3], [ 1, 5 ]], 
[[0, 4, 2], [ 3, 1, 5 ]], 
...
[[0, 1, 2], [ 3, 4 ], [ 5 ]], 
...
[[0, 4, 2], [ 3, 1 ], [ 5 ]],
...
]

Since this has been flagged as duplicate of another question that's not even close to this one, here is a complete output array where input array is [ 0, 1, 2 ] 

[
[ [ 0, 1, 2 ] ],
[ [ 0, 2, 1 ] ],
[ [ 1, 0, 2 ] ],
[ [ 1, 2, 0 ] ],
[ [ 2, 1, 0 ] ],
[ [ 2, 0, 1 ] ],
[ [ 0 ], [ 1, 2 ] ],
[ [ 0 ], [ 2, 1 ] ],
[ [ 1 ], [ 0, 2 ] ],
[ [ 1 ], [ 2, 0 ] ],
[ [ 2 ], [ 0, 1 ] ],
[ [ 2 ], [ 1, 0 ] ],
[ [ 0 ], [ 1 ], [ 2 ] ]
]
  • For this array of 3 elements there are 13 sets of subsets.
  • A set can contain 1 to 3 subsets.
  • Inside every set, regardless of the number of subsets there are always 3 elements.
  • Any element appears only once in a subset and only once in a set.
  • Elements do permutate inside a set. [ [ 0 ], [ 1, 2 ] ] is not the same as [ [ 0 ], [ 2, 1 ] ].
  • Subsets do not permutate. It's a combination. [ [ 0 ], [ 1 ], [ 2 ] ] and [ [ 2 ], [ 1 ], [ 0 ] ] are the same set.

I am trying to construct a routing algorithm where all elements inside the subsets are way points while the subsets represent routes.

Here is what I have so far: 

function my_function($in,$min,$max){
    $out = array();
    for($i=$min; $i<$max+1; $i++){   // $i is the number of subsets in each set

        $sets = ??                       // all I know so far is that if $i=1 $i=P(count($in),count($in))
                                        // since for $i=1 all the sets contain all permutations of the elements inside $in
        for($j=0; $j<$sets; $j++){
            array_push($out,array());
            //construct sets of subsets
        }
    }
    return $out;
}

These are a few functions to use: 

function fact($x){                          // !X
    return gmp_strval(gmp_fact($x));
}
function C($n,$r){                          // nCr
    return fact($n)/fact($r)/fact($n-$r);
}
function P($n,$k){                          // nPk
    return fact($n)/fact($n-$k);
}
function pc_permute($items, $perms = array( )) {    //samples permutations
    if (empty($items)) {
        $return = array($perms);
    }  else {
        $return = array();
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
         list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             $return = array_merge($return, pc_permute($newitems, $newperms));
         }
    }
    return $return;
}

If you can help with as little as a small suggestion please do. If you don't understand, don't just flag my question to be a duplicate of another that's not even close to be this complex. Thank you!

Horia
  • 15
  • 5
  • See if this helps: http://stackoverflow.com/questions/1679605/combinations-dispositions-and-permutations-in-php you might have to customize your solution based on that answer. Starting with a smaller array would be helpful. – Maximus2012 Jun 09 '15 at 19:14
  • Another one: http://stackoverflow.com/questions/10222835/get-all-permutations-of-a-php-array you might want to make some changes first based on these solutions and then come back and post your code here if you still run into issues. – Maximus2012 Jun 09 '15 at 19:15
  • @Maximus2012 Hi, I have a function that outputs permutations. For the first level (only 1 subset per set) I will just run it through that. For the 2nd level (2 per set), I start with [ [ 0 ], [ 1, 2, 3, 4, 5] ] than permutate the 2nd subset till [ [ 5 ], [ 1, 2, 3, 4, 0] ] . Do I have to stop where I have X/2+1 elements in the first array so I don't run into duplicates? Subset order does not count. – Horia Jun 09 '15 at 19:48
  • Please update your question with this additional information and/or any php code that you might have. This will allow SO users to help you better. – Maximus2012 Jun 09 '15 at 20:16
  • This is not specific size and it's not just combinations. It's actually sets of combinations of subsets of unspecified sizes including permutations of X elements where sum of subset sizes of a set equal to X. – Horia Jun 09 '15 at 21:07
  • @Maximus2012 Hi, I have 2 functions that I need to combine. Please have a look as I have no idea how. – Horia Jun 09 '15 at 21:21
  • Look at other question whose duplicate this question is and see if it helps. If it does not then you might want to update your question with additional information. – Maximus2012 Jun 10 '15 at 19:23
  • @Maximus2012 Hi, I don't understand why everyone marks this as a duplicate. The other question is about same size sets. The pers. who posted wanted sets like this: AA, AB, AC and AAA ABB ABC. I have a whole army of people who flag it as a duplicate, although it has nothing to do with it. I don't see how I can explain better than this. I gave all the dos and donts and I put an example that shows clearly the algorithm. Please someone explain to me how this is the same. The only thing that is the same is that it mentions the word SETS. I can't even use parts of that question. – Horia Jun 10 '15 at 23:45
  • I don't even have enough reputation to mark question as duplicate. I think you should look at the solution in that other question and use that as a reference for building your solution. If that does not work then you can post another question with clearly indicating what you tried, what worked, what did not work and what is the expected output. – Maximus2012 Jun 11 '15 at 13:43
  • Check out the new answer regarding this post [here](http://stackoverflow.com/a/30788457/3709765) :) – someOne Jun 11 '15 at 18:20
  • Also, I've flagged for moderator intervention :) – someOne Jun 11 '15 at 18:48

0 Answers0