Asked  7 Months ago    Answers:  5   Viewed   37 times

What is the most efficient way to generate all the combinations, dispositions and permutations of an array in PHP?

 Answers

24

Here is code to get all permutations:

http://php.net/manual/en/function.shuffle.php#90615

With the code to get the power set, permutations are those of maximal length, the power set should be all combinations. I have no idea what dispositions are, so if you can explain them, that would help.

Wednesday, March 31, 2021
 
max_
answered 7 Months ago
68

The solution is to ensure that you are using the mysqlnd driver for php.

How do you know that you're not using mysqlnd?

When viewing php -i, there will be no mention of "mysqlnd". The pdo_mysql section will have something like this:

pdo_mysql

PDO Driver for MySQL => enabled Client API version => 5.1.72

How do you install it?

Most installation guides for L/A/M/P suggest apt-get install php5-mysql but the native driver for MySQL is installed by a different package: php5-mysqlnd. I found that this was available with the ppa:ondrej/php5-oldstable.

To switch to the new driver (on Ubuntu):

  • Remove the old driver:
    apt-get remove php5-mysql
  • Install the new driver:
    apt-get install php5-mysqlnd
  • Restart apache2:
    service apache2 restart

How do I check that the driver is being used?

Now php -i will mention "mysqlnd" explicitly in the pdo_mysql section:

pdo_mysql

PDO Driver for MySQL => enabled
Client API version => mysqlnd 5.0.10 - 20111026 - $Id:      e707c415db32080b3752b232487a435ee0372157 $

PDO settings

Ensure that PDO::ATTR_EMULATE_PREPARES is false (check your defaults or set it):
$pdo->setAttribute(PDO::ATTR_EMULATE_PREPARES, false);

Ensure that PDO::ATTR_STRINGIFY_FETCHES is false (check your defaults or set it):
$pdo->setAttribute(PDO::ATTR_STRINGIFY_FETCHES, false);

Returned values

  • Floating-point types (FLOAT, DOUBLE) are returned as PHP floats.
  • Integer types (INTEGER, INT, SMALLINT, TINYINT, MEDIUMINT, BIGINT †) are returned as PHP integers.
  • Fixed-Point types (DECIMAL, NUMERIC) are returned as strings.

† BIGINTs with a value greater than a 64 bit signed int (9223372036854775807) will return as a string (or 32 bits on a 32 bit system)

    object(stdClass)[915]
      public 'integer_col' => int 1
      public 'double_col' => float 1.55
      public 'float_col' => float 1.5
      public 'decimal_col' => string '1.20' (length=4)
      public 'bigint_col' => string '18446744073709551615' (length=20)
Tuesday, June 8, 2021
 
SkyNet
answered 5 Months ago
98
public static long combination(long n, long k)
    {
        double sum=0;
        for(long i=0;i<k;i++)
        {
            sum+=Math.log10(n-i);
            sum-=Math.log10(i+1);
        }
        return (long)Math.pow(10, sum);
    }
Friday, July 23, 2021
 
Len_D
answered 3 Months ago
57

I noticed that your updated getPerms function contains duplicates. Here's my crack at a dupe-free version. Hopefully the comments speak for themselves. The hardest part was writing an efficient distrib function, because the concatenation operator has to be used somewhere. Luckily it's only used on small sublists, so the performance remains reasonable. My getAllPerms code below generates all permutations of [1..9] in around a quarter of a second, all 10-element permutations in around 2.5 seconds.

Edit: funny, I didn't look at Tomas' code, but his combinations function and my picks function are nearly identical.

// All ordered picks {x_i1, x_i2, .. , x_ik} of k out of n elements {x_1,..,x_n}
// where i1 < i2 < .. < ik
let picks n L = 
    let rec aux nleft acc L = seq {
        match nleft,L with
        | 0,_ -> yield acc
        | _,[] -> ()
        | nleft,h::t -> yield! aux (nleft-1) (h::acc) t
                        yield! aux nleft acc t }
    aux n [] L

// Distribute an element y over a list:
// {x1,..,xn} --> {y,x1,..,xn}, {x1,y,x2,..,xn}, .. , {x1,..,xn,y}
let distrib y L =
    let rec aux pre post = seq {
        match post with
        | [] -> yield (L @ [y])
        | h::t -> yield (pre @ y::post)
                  yield! aux (pre @ [h]) t }
    aux [] L

// All permutations of a single list = the head of a list distributed
// over all permutations of its tail
let rec getAllPerms = function
    | [] -> Seq.singleton []
    | h::t -> getAllPerms t |> Seq.collect (distrib h)

// All k-element permutations out of n elements = 
// all permutations of all ordered picks of length k combined
let getPerms2 n lst = picks n lst |> Seq.collect getAllPerms

Edit: more code in response to comments

// Generates the cartesian outer product of a list of sequences LL
let rec outerProduct = function
    | [] -> Seq.singleton []
    | L::Ls -> L |> Seq.collect (fun x -> 
                outerProduct Ls |> Seq.map (fun L -> x::L))

// Generates all n-element combination from a list L
let getPermsWithRep2 n L = 
    List.replicate n L |> outerProduct  
Sunday, August 1, 2021
 
Mihail Feraru
answered 3 Months ago
58

While I really appreciate the efforts from @tucuxi and @David Eisenstadt, I found some issues with the Hamiltonian approach, namely that it didn't solve for certain values of n and k and certain elements were also unnecessarily discriminated.

I decided to give the ideas listed in my question a go (hit count table) and it seems to give pretty good results. This solution however also requires a post-generation sorting which does not fulfill the on-demand bonus requirement. For reasonable n and k this should be feasible though.

Admittedly, I've found that my algorithm sometimes seems to favour combinations that result in consecutive appearances for one element, which can probably be tuned. But as of now, my algorithm might be inferior to tucuxi's for (7,4) specifically. It does however present a solution for every n, k and seems to discriminate elements less.

My code is listed below.

Thanks again.

public class CombinationGenerator {
    private final int N;
    private final int K;
    private final int[] mCurrentCombination;

    public CombinationGenerator(int n, int k) {
        N = n;
        K = k;
        mCurrentCombination = new int[k];

        setElementSequence(0, 0);
        mCurrentCombination[K - 1]--; // fool the first iteration
    }

    private void setElementSequence(int startPos, int startValue) {
        for (int i = startPos; i < K; i++) {
            mCurrentCombination[i] = i + startValue - startPos;
        }
    }

    public int[] getNextCombination() {
        for (int i = K - 1; i >= 0; i--) {
            if (mCurrentCombination[i] < i + N - K) {
                setElementSequence(i, mCurrentCombination[i] + 1);
                return mCurrentCombination.clone();
            }
        }

        return null;
    }   
}

public class CombinationSorter {
    private final int N;
    private final int K;

    public CombinationSorter(int n, int k) {
        N = n;
        K = k;
    }

    public List<int[]> getSortedCombinations(List<int[]> combinations) {
        List<int[]> sortedCombinations = new LinkedList<int[]>();
        int[] combination = null;
        int[] hitCounts = new int[N]; // how many times each element has been
                                      // used so far

        // Note that this modifies (empties) the input list
        while (!combinations.isEmpty()) {
            int index = findNextCombination(combinations, hitCounts, combination);
            combination = combinations.remove(index);
            sortedCombinations.add(combination);

            addHitCounts(combination, hitCounts);
        }

        return sortedCombinations;
    }

    private int findNextCombination(List<int[]> combinations, int[] hitCounts,
            int[] previousCombination) {
        int lowestHitCount = Integer.MAX_VALUE;
        int foundIndex = 0;

        // From the remaining combinations, find the one with the least used
        // elements
        for (int i = 0; i < combinations.size(); i++) {
            int[] comb = combinations.get(i);
            int hitCount = getHitCount(comb, hitCounts);

            if (hitCount < lowestHitCount) {
                lowestHitCount = hitCount;
                foundIndex = i;
            } else if (hitCount == lowestHitCount
                    && previousCombination != null
                    && getNrCommonElements(comb, previousCombination) < getNrCommonElements(
                            combinations.get(foundIndex), previousCombination)) {
                // prefer this combination if hit count is equal but it's more
                // different from the previous combination in our sorted list
                // than what's been found so far (avoids consecutive element
                // appearances)
                foundIndex = i;
            }
        }

        return foundIndex;
    }

    private int getHitCount(int[] combination, int[] hitCounts) {
        int hitCount = 0;

        for (int i = 0; i < K; i++) {
            hitCount += hitCounts[combination[i]];
        }

        return hitCount;
    }

    private void addHitCounts(int[] combination, int[] hitCounts) {
        for (int i = 0; i < K; i++) {
            hitCounts[combination[i]]++;
        }
    }

    private int getNrCommonElements(int[] c1, int[] c2) {
        int count = 0;

        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                if (c1[i] == c2[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

public class Test {
    public static void main(String[] args) {
        final int n = 7;
        final int k = 3;

        CombinationGenerator cg = new CombinationGenerator(n, k);
        List<int[]> combinations = new LinkedList<int[]>();
        int[] nc;

        while ((nc = cg.getNextCombination()) != null) {
            combinations.add(nc);
        }

        for (int[] c : combinations) {
            System.out.println(Arrays.toString(c));
        }

        System.out.println("Sorting...");

        CombinationSorter cs = new CombinationSorter(n, k);
        List<int[]> sortedCombinations = cs.getSortedCombinations(combinations);

        for (int[] sc : sortedCombinations) {
            System.out.println(Arrays.toString(sc));
        }
    }

}

Results for (7,4):

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

Results for (5,2):

[0, 1]
[2, 3]
[0, 4]
[1, 2]
[3, 4]
[0, 2]
[1, 3]
[2, 4]
[0, 3]
[1, 4]
Tuesday, October 19, 2021
 
MilanSxD
answered 6 Days ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :