Permutations - All Possible Sets of Numbers

Permutations - all possible sets of numbers

You're looking for the permutations formula:

nPk = n!/(n-k)!

In your case, you have 9 entries and you want to choose all of them, that's 9P9 = 9! = 362880

You can find a PHP algorithm to permutate in recipe 4.26 of O'Reilly's "PHP Cookbook".

pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8));

Copied in from O'Reilly:

function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join(' ', $perms) . "\n";
    }  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, $newperms);
         }
    }
}

Permutations for all possible sets ( 3 digits) including zero

You can do a preg_match on numbers by creating regular expression such as:

/^[235046]+$/

This means we are trying to match a string which has digits 235046(meaning, 2 or 3 or 5 and so on) right from start (^ caret symbol) till end ($ dollar symbol). If we find a match, we collect them in another array.

Snippet:

<?php

$digits = '235046';

$single_chart_filtered = [];

foreach($single_chart as $chart_value){
    if(preg_match("/^[$digits]+$/",$chart_value) === 1){
        $single_chart_filtered[] = $chart_value;
    }
}

print_r($single_chart_filtered);

$double_chart_filtered = [];

foreach($double_chart as $chart_value){
    if(preg_match("/^[$digits]+$/",$chart_value) === 1){
        $double_chart_filtered[] = $chart_value;
    }
}

Demo: https://3v4l.org/jChvm

Finding all possible combinations of numbers to reach a given sum

This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue
    
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 
   

if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

This type of algorithms are very well explained in the following Stanford's Abstract Programming lecture - this video is very recommendable to understand how recursion works to generate permutations of solutions.

Edit

The above as a generator function, making it a bit more useful. Requires Python 3.3+ because of yield from.

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Here is the Java version of the same algorithm:

package tmp;

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

It is exactly the same heuristic. My Java is a bit rusty but I think is easy to understand.

C# conversion of Java solution: (by @JeremyThompson)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby solution: (by @emaillenin)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Edit: complexity discussion

As others mention this is an NP-hard problem. It can be solved in exponential time O(2^n), for instance for n=10 there will be 1024 possible solutions. If the targets you are trying to reach are in a low range then this algorithm works. So for instance:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generates 1024 branches because the target never gets to filter out possible solutions.

On the other hand subset_sum([1,2,3,4,5,6,7,8,9,10],10) generates only 175 branches, because the target to reach 10 gets to filter out many combinations.

If N and Target are big numbers one should move into an approximate version of the solution.

All possible combinations and permutations of size n algorithm

Your task (all permutations of all combinations) can be easily solved using regular recursive function (as I did below) without any fancy algorithm.

Try it online!

#include <vector>
#include <functional>
#include <iostream>

void GenCombPerm(size_t n, size_t k, auto const & outf) {
    std::vector<bool> used(n);
    std::vector<size_t> path;
    std::function<void()> Rec =
        [&]{
            if (path.size() >= k) {
                outf(path);
                return;
            }
            for (size_t i = 0; i < used.size(); ++i) {
                if (used[i])
                    continue;
                used[i] = true;
                path.push_back(i);
                Rec();
                path.pop_back();
                used[i] = false;
            }
        };
    Rec();
}

int main() {
    std::vector<size_t> a = {1, 2, 3};
    GenCombPerm(a.size(), 2, [&](auto const & v){
        std::cout << "[";
        for (auto i: v)
            std::cout << a[i] << ", ";
        std::cout << "], ";
    });
}

Output:

[1, 2, ], [1, 3, ], [2, 1, ], [2, 3, ], [3, 1, ], [3, 2, ], 

Listing all permutations of a given set of values

You can choose between performance, particular distribution and simplicity. By a particular distribution I mean, whether you care about some particular order, such as lexicographic, of the output.

The best performing algorithm to my knowledge is the Steinhaus algorithm. It is optimal up to a multiplicative constant in the sense that only a constant number of processor instructions are necessary to generate one permutation (not counting the instructions necessary to print it out which is not always needed).

There is also a very simple algorithm that produces the permutations in the lexicographic order that you will probably be able to reinvent as a recursive procedure yourself, and whose performance is O(n.log(n).log(n)), therefore roughly the same as generating the list by any other method and sorting it.

Edit: here is pseudocode of the simple algorithm:

void permute(Element[] permutationPrefix, Set rest)
{
    if (rest.IsEmpty) {
        // permutationPrefix is now a full permutation
        print(permutationPrefix);
    } else {
        foreach (element in rest) {
            permutationPrefix.Append(element);
            permute(permutationPrefix, rest.Minus(element))
            permutationPrefix.Length--;  // cut away the last item
        }
    }
}

Initially call this with an empty permutationPrefix and rest holding the full set; if this set is a sorted data structure, the permutations will be output in the lexicographic order.

Note that we are copying and modifying the set at each recursive call, which is the most expensive operation of the whole algorithm, possibly together with the print method. The cost of a single set copy is logarithmic in the total number of permutations n; and because the depth of the recursive call stack is also logarithmic, the O(n.log(n).log(n)) performance estimate follows.

(This algorithm is also suitable for conversion into a well behaved random permutation generator.)

---

Related Topics