5
\$\begingroup\$

I am using this function to find all permutation of objects of a given length. However, right now, the maximum length I can reach before it throws an "Out of memory exception" is 9 (also, it gets too slow from 7 onwards)

IEnumerable<IEnumerable<T>> PermutationOfObjects<T>(IEnumerable<T> objects, int length)
{
    if (length == 1)
        return objects.Select(t => new T[] { t });

    return PermutationOfObjects(objects, length - 1).SelectMany(t => objects, (t1, t2) => t1.Concat(new T[] { t2 }));
}

Could someone suggest any improvements, so that I could increase the max length limit ?

EDIT

To avoid confusion, I must add that the code will not just produce permutations. As @RobH mentions it in the answer.

For a given input set {a,b,c}, the result will be {a,a,a} , {a,a,b}, {a,a,c}, and other similar sets along with the ones that can be called valid permutations.

For the lack of better choice than permutations of combinations, I am not changing the topic. Please feel free to change the topic of the question if it can be made clearer.

EDIT 2

Explanation on why the program does, what it does:

The idea is to check if a combination of n objects is valid (Validity, here can be subjective, for the sake of simplicity say, that the given combination is valid if it has a total Price more than 1000).

Now, for an input set, {a,b,c} and a length 3, I check how many combinations which can be made from the input set are valid. These combinations allow repition of objects. i.e. {a} can be used anywhere from 1 to the maxlength times (3, here). As the order in which I have the materials is also important ({a,b,c} != {b,a,c}), hence permutation.

What I do is , I find all results for a given input and length and then iterate them to check if they satisfy the validity criteria. It works fine till 6, starts getting uber slow from 7 onwards and finally breaks at 9 or 10.

EDIT 3

Adding sample code to test the given function:

 static class Program
{        
    static void Main()
    {
        int maxLength = 10; // 8 is the maximum length that can be supported right now

        List<OBJECT> objectList = new List<OBJECT>();
        OBJECT obj;
        obj = new OBJECT();
        obj.Price = 2000;
        obj.Name = "A";
        objectList.Add(obj);
        obj = new OBJECT();
        obj.Price = 1900;
        obj.Name = "B";
        objectList.Add(obj);
        obj = new OBJECT();
        obj.Price = 1600;
        obj.Name = "C";
        objectList.Add(obj);
        obj = new OBJECT();
        obj.Price = 200;
        obj.Name = "D";
        objectList.Add(obj);
        obj = new OBJECT();
        obj.Price = 600;
        obj.Name = "E";
        objectList.Add(obj);
        obj = new OBJECT();
        obj.Price = 6000;
        obj.Name = "F";
        objectList.Add(obj);
        obj = new OBJECT();
        obj.Price = 5000;
        obj.Name = "G";
        objectList.Add(obj);
        obj = new OBJECT();
        obj.Price = 5500;
        obj.Name = "H";
        objectList.Add(obj);

        IEnumerable<IEnumerable<OBJECT>> allPermutations = PermutationOfObjects(objectList, maxLength);

        //Ordering by price
        allPermutations = from permutation in allPermutations
                              orderby permutation.Sum(x => x.Price)
                              select permutation;

        allPermutations = from permutation in allPermutations
                          where permutation.Sum(x => x.Price) < 10000
                          select permutation;


        if (allPermutations.Any())
        {
            foreach (var r in allPermutations)
            {
                // Do things
            }
        }
    }

    public static IEnumerable<IEnumerable<T>> PermutationOfObjects<T>(IEnumerable<T> objects, int length)
    {
        if (length == 1)
            return objects.Select(t => new T[] { t });

        var combinations = PermutationOfObjects(objects, length - 1).SelectMany(t => objects, (t1, t2) => t1.Concat(new T[] { t2 }));
        return combinations;
    }

}

public class OBJECT
{
    public string Name = "";
    public int Price = 0;
}
\$\endgroup\$
10
  • \$\begingroup\$ As RobH already mentioned, the slowdown and memory consumption is not caused by this piece of code, but by the code that uses it. You may want to include the calling code in your post if you want more accurate reviews. \$\endgroup\$ – Pieter Witvoet Sep 12 '17 at 9:34
  • \$\begingroup\$ @PieterWitvoet, have added a sample code for replicating the problem scenario \$\endgroup\$ – RMad9248 Sep 12 '17 at 9:51
  • \$\begingroup\$ Increasing the limit in your sample makes things slower, obviously, but I'm not seeing any memory problems. Is this your actual code? \$\endgroup\$ – Pieter Witvoet Sep 12 '17 at 10:51
  • 1
    \$\begingroup\$ OrderBy buffers to an array. You cannot create an array in .Net that can store 10^10 items. Remove the order by and it will still be really slow but it won't blow up. \$\endgroup\$ – RobH Sep 12 '17 at 13:37
  • 1
    \$\begingroup\$ Sum is commutative. This may be a start. \$\endgroup\$ – paparazzo Sep 12 '17 at 13:46
4
\$\begingroup\$
        //Ordering by price
        allPermutations = from permutation in allPermutations
                              orderby permutation.Sum(x => x.Price)
                              select permutation;

        allPermutations = from permutation in allPermutations
                          where permutation.Sum(x => x.Price) < 10000
                          select permutation;

orderby is eager: it can't find the smallest element without reading all of them, and it can't read them and not store them because in general an IEnumerable doesn't guarantee to be free of side-effects.

Moreover, orderby does comparison-based sorting, not radix-based, so it's superlinear time.

where, on the other hand, is both lazy and linear. So if you're going to split the two operations up, you should most certainly do the where before the orderby.

I can't, however, see any advantage to splitting them up. So

        //Ordering by price
        allPermutations = from permutation in allPermutations
                              where permutation.Sum(x => x.Price) < 10000
                              orderby permutation.Sum(x => x.Price)
                              select permutation;

is unconditionally an improvement, and looking at your example data, in practice it should avoid you running out of memory.


        if (allPermutations.Any())
        {
            foreach (var r in allPermutations)
            {
                // Do things
            }
        }

The if is completely pointless: a foreach loop over an empty enumerable does nothing: it doesn't throw an exception or whatever error you're trying to avoid.


A suitable name for this method would be CartesianPower. A non-recursive implementation can be written which simply counts from 0 to Math.Pow(objects.Count(), length)-1 in base objects.Count(), then converts each digit to the corresponding object.

\$\endgroup\$
1
\$\begingroup\$

The computational complexity of your code is \$O(N^N)\$ where N is the number of your initial elements. So in terms of speed it should be very slow with N = 10 already cause it needs to look at 10 billion permutations, which is a lot. Don't even try to run it with N = 20 because you won't ever be able to see it end.

In terms of memory usage, it depends on your needs. If you absolutely need tp store all the permutations in memory at once - you are probably out of luck by the same reason - it will use \$O(N^N)\$ memory in the worst case.

But if it's okay to process 'valid' permutations one at a time - the code can be rewritten so that it uses only \$O(N)\$ memory, which is in your case very little, because N is very small (otherwise the program will never end, remember?).

There are probably many ways to rewrite the code using LINQ, but you have to be careful and understand laziness/eagerness of LINQ operation, and, in my opinion, it can be a little bit harder to debug.

So in case you are not required to use LINQ, please have a look at the code that does it with plain C# statements. It probably loses in genericity and isn't so elegant as LINQ, but in my opinion it's easier to edit and debug. You have more control over the logic of recursion and can optimize it as much as possible (depending on how much knowledge you have about your initial data) by returning early from 'bad' recursion branches. Its worst computational case is still \$O(N^N)\$ of course, but if have good insights about your data and optimize recursion accordingly or you are just lucky - in practice it may be much faster. Memory usage is \$O(N)\$ unless you explicitly store all valid permutations in some field or variable.

interface IHasPrice {
    int Price {get;}
}

class Foo : IHasPrice {
    public int Price { get; set; }
}

class PermutationFinder<T> where T : IHasPrice {
    private int[] _indexes;
    private IList<T> _objects;

    public void FindPermutations(IList<T> objects) {
        _objects = objects;
        _indexes = new int[objects.Count];

        FindPermutationsRecursively(0, 0);
    }

    // we keep currentIdx as the main variable of the recursion to know 
    // how many elements of a permutation we've already chosen
    // and we keep currentPrice so we can cut out 'bad' branches of our 
    // recursion tree as early as possible, when we already know there 
    // won't be 'valid' permutation down this branch
    void FindPermutationsRecursively(int currentIdx, int currentPrice)
    {
        // in case you need to check your permutations against different criteria - 
        // you can pass a simple delegate from the calling side that checks whether 
        // we should stop current branch
        // this way no need to copy paste whole method just to change this 10000 constant
        if (currentPrice > 10000) {
            return;
        }

        // base case. We have a valid permutation - let's reconstruct it from our saved indexes and process
        if (currentIdx == _objects.Count)
        {
            var combination = ReconstructPermutation(_objects);
            ProcessPermutation(combination);
            return;
        }

        // position every object at the next index and make a recursive call with updated index and price
        for (int i = 0; i < _objects.Count; ++i) {
            _indexes[currentIdx] = i; 
            FindPermutationsRecursively(currentIdx + 1, currentPrice + _objects[i].Price);
        }
    }

    void ProcessPermutation(IList<T> objects) {
        // do whatever needed

        // if you need to save all combinations somewhere for later processing, 
        // better use some sort of database or other persistent storage,
        // because saving it in IList<IList<T>> allFoundCombination field, for example, 
        // will again cause 'Out of memory exception' if lots of permutations are 'valid' 
    }

    IList<T> ReconstructPermutation(IList<T> objects) {
        T[] combination = new T[objects.Count];
        for (int i = 0; i < _indexes.Length; ++i) {
            int index = _indexes[i];
            combination[i] = objects[index];
        } 
        return combination;
    }
}

class Program
{
    static void Main(string[] args)
    {
        List<IHasPrice> objectList = new List<IHasPrice>() {
            new Foo() {Price = 2000},   
            new Foo() {Price = 1900},   
            new Foo() {Price = 1600},   
            new Foo() {Price = 200},   
            new Foo() {Price = 600},   
            new Foo() {Price = 6000},   
            new Foo() {Price = 5000},   
        };            

        var combinationFinder = new PermutationFinder<IHasPrice>();
        combinationFinder.FindPermutations(objectList);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.