Algorithm for permutations

Question

I am looking for an efficient combinations function that would take into account the order of the array. For example I want to generate all of the combinations of "hello world" but I don't want any of it reversed "world hello". I currently have a combinations function but it's too much.

Simple example :

$text = "Hello World"
$arr = explode(" ",$text); // string to array

And gives:

$result = combo_function($arr);
var_dump($result);

"Hello World"
"Hello" 
"World"

I do NOT want the inverse:

"World Hello"

the key is that I want it to be faster than combinations if possible.

Currently I am using this:

 // careful, this is very labor intensive ( O(n^k) )

public function buildSearchCombinations(&$set, &$results)
{
    for ($i = 0; $i < count($set); $i++) {

        $results[] = (string) $set[$i];
        $tempset = $set;
        array_splice($tempset, $i, 1);
        $tempresults = array();
        $this->buildSearchCombinations($tempset, $tempresults);

        foreach ($tempresults as $res) {
            $results[] = trim((string) $set[$i]) . " " . (string) trim($res);
        }
    }
}

What do you mean with "combination of hello world"? All combinations of the order of your words? — Schokokuchen Bäcker
– Schokokuchen Bäcker, Commented Mar 12, 2017 at 15:27
it's really unclear what you want to accomplish here! your example hello world is really poor to understand what are you trying to do! — hassan
– hassan, Commented Mar 12, 2017 at 15:42
Basically I am trying to create a set of permutations to use in a Database search but instead of using ALL combinations, we can assume that the user has to enter them in order. So for example if they are searching "French Fries" it will return say all of the restaurants serving them. Where if they were to enter in Fries French, it will fail. Currently I am using combinations which will automatically generate "French Fries" and "Fries French" along with "Fries" and "French". This is too much work with larger phrases. — Mike Q
– Mike Q, Commented Mar 12, 2017 at 22:01
Answer to your deleted question: How can I sort an Apache log file by date? — Cyrus
– Cyrus, Commented Mar 13, 2017 at 18:08

apokryfos · Accepted Answer · 2017-03-12 16:46:05Z

1

I have a rather odd solution to this:

<?php

function supersetmember($set, $index) {
    $keys = array_reverse(str_split(decbin($index)));
    $member = [];
    foreach ($keys as $k => $v) {
        if ($v == 1) { 
            $member[] = $set[$k];
        }

    }
    return $member;
}


$text = "Hello World";
$arr = explode(" ",$text);
$total = pow(2,count($arr)); //Total permutations on size of set n is 2^n 
$superset = [];
for ($i = 0;$i < $total;$i++) {
    $superset[] = supersetmember($arr,$i);
}
print_r($superset);

Explanation:

There's 2^n sets that constitute a set of size n (including the empty set). You can map each of those sets as a natural number from 0 to (n-1). If you convert that number to binary then the digits that are 1 will indicate which members of the original set your subset will contain. Example:

Set = (A,B);

Superset member 2(decimal) = 10 (binary) which means the subset will include the second but not first member (we read the number from right to left as in from least significant to most significant digit).

The advantage of doing this is that you have a sort of a "fausset" algorithm (function supersetmember) which you give it a set and the subset you want and you get that subset.

The complexity of getting a single subset in the current version is O(n) but if you implement it with bit shifting you can reduce it to O(log n) In total the algorithm will be O(2^n) which is unavoidable because there are O(2^n) subsets to be generated.

answered Mar 12, 2017 at 16:46

apokryfos

40.9k11 gold badges85 silver badges128 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Mike Q Over a year ago

Wow dude, this is totally badass

apokryfos Over a year ago

@MikeQ if you want to share how you used this code, the generally accepted convention here is to update your question.

Mike Q Over a year ago

ok thx, I forgot that I should have done it that way... I blame it on it being the weekend. thanks

Collectives™ on Stack Overflow

Algorithm for permutations

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related