Futz testing arsort() dependent code?

Question

It seems that a large, complicated codebase depends on the order arsort produces. Before I dive in to discern what's actually happening in like 50 classes -- is there a simple way to shuffle items with equal values?

In other words, if the input is

['foo' => 3, 'bar' => 3, 'baz' => 3, 'this' => 2,  'that' => 2]

I'd like to get

['baz' => 3, 'bar' => 3, 'foo' => 3, 'this' => 2,  'that' => 2]

one run maybe, then

['baz' => 3, 'bar' => 3, 'foo' => 3, 'that' => 2,  'this' => 2]

on another random run.

I second @Ghost - for shuffling an array, you should use the Fisher Yates algorithm: http://stackoverflow.com/questions/3169805/how-can-i-randomize-an-array-in-php-by-providing-a-seed-and-get-the-same-order — Centril, Sep 25 '14 at 04:05
@Centril but I most definitely do not want the same order, I want all possible orders to happen on subsequent runs. — chx, Sep 25 '14 at 04:11
As far as i understand it from your example, you want to shuffle the sets {baz,bar,foo} and {that,this} independently of each other... Shuffling gives no guarantee that all possible orders will be included, but it is likely to happen eventually. — Centril, Sep 25 '14 at 04:17
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/61878/discussion-between-chx-and-centril). — chx, Sep 25 '14 at 08:24

Centril · Accepted Answer · 2014-09-25T08:43:13.337

How about something like this? (Untested)

Worst Case complexity: O(k)

Note: Written for algorithmic clarity and not PHP details...

function shuffleInput( $data ) {
    // Separate into sets.
    $sets = [];
    foreach ( $data as $k => $v ) {
        $sets[$v][] = $k;
    }

    // Shuffle & Join.
    $data = [];
    foreach ( $sets as $v => &$set ) {
        shuffle( $set );
        foreach( $set as $k ) {
            $data[$k] = $v;
        }
    }
    return $data;
}

Depending on the size of your input, it might be a better idea to unset every element in $data in the first loop instead of just creating a new array. This applies if data is very large and memory is precious to you - as well as reducing any sudden spikes & dips in memory usage.

Also, if you're going to continously shuffle the same $data around you might want to separate out the making of $sets to some other place or at least allow the developer to pass/get it as a side effect.

After the shuffle you can do `call_user_func_array('array_merge', $set)` instead of the foreach. — chx, Sep 25 '14 at 08:15
Nope, you can't because $set is of "type" array[index => $k] and not [$k => $v] which you need. Besides, if you want to call array_merge you can do it without superfluous reflection. I believe what I've is the most efficient way there is... Improvements possible: make C call for what the foreach does - namely: array_add($dest, $keys, $value_for_all); Also: Provide a way to array_pop in a foreach and access the key so as to make $data already empty when reaching the reset line. — Centril, Sep 25 '14 at 08:33

Cheery · Answer 2 · 2014-09-25T04:37:55.703

If you do not want to deal with shuffle, but rather prefer to check all permutations of the array, then you can do something like this:

$arr = array('foo' => 3, 'bar' => 3, 'baz' => 3, 'this' => 2,  'that' => 2);
$keys = array_keys($arr);
$indexes = range(0, count($arr) - 1);

pc_permute($indexes, $perms);

var_dump($perms);

function pc_permute($items, &$ret = array(), $perms = array( )) {
    if (empty($items)) { 
        $ret[] = $perms;
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $ret, $newperms);
         }
    }
}

Array $perms will give all permutations of the indexes, key name by index you can get from $keys and value by key or index (use array_slice) from $arr :)

ps: but you should understand - more elements you have in the original array, more permutations you will find. if there are n elements then there will be n! permutations. for n = 5 there are 120 permutations.

Ouch, that's an interesting thought, but kinda unusable due to O(n!) ^^ — Centril, Sep 25 '14 at 04:47

Futz testing arsort() dependent code?

2 Answers2