Generate all the possible permutations of a class

Question

I have the following classes. For testing purpose, I would like to get all the possible permutations of the class Client. I know that the number can be very large, but this is not my problem for now.

Client: No (int), Name(string), Address(Address object)
Address: Street(string), Country(string), etc.

For a property of type int, I always try the same three values (-1, 0, 1), for string (null, string.Empty, "Hello World", etc.). For the base types, it works well. However, for the class Address, this is different.

In brief, I am trying to write a method generic enough to take any Type (class, etc.) and get all the possible permutations (in other words: public IEnumerable GetPermutations(Type myType)). With the help of .NET Reflection, this method would loop on all the settable properties.

Does anybody have an idea how to do that?

Thanks

where do you get the values from? do you have a list of allowed values, for example? — Aziz
– Aziz, Commented Apr 6, 2009 at 19:13
@Aziz: He is asking for a brute force for each possible value. — Samuel
– Samuel, Commented Apr 6, 2009 at 19:13
How much work do you have done already? What is the part you're having trouble with (ie. generating the permuations, storing the address info, using reflection, etc...)? — Robert Gowland
– Robert Gowland, Commented Apr 6, 2009 at 19:28

Dmitri Nesteruk · Accepted Answer · 2009-04-06 19:14:05Z

4

The PEX testing framework does something along the lines. It attempts to provide several permutations of method parameters such that potentially useful test cases are covered.

answered Apr 6, 2009 at 19:14

Dmitri Nesteruk

23.9k23 gold badges107 silver badges169 bronze badges

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

Comments

kvb · Accepted Answer · 2009-04-06 19:53:16Z

2

Here's a class that may get you started, though I haven't tested it much. Note that this will only work for classes that have a no-args constructor, and won't work for some types of recursive classes (e.g. a class with a property of its own type, such as a tree). You also may want to pre-populate more classes in the static constructor.

public static class PermutationGenerator
{
    private static class Permutation<T>
    {
        public static IEnumerable<T> Choices { get; set; }
    }

    static PermutationGenerator()
    {
        Permutation<int>.Choices = new List<int> { -1, 0, 1 }.AsReadOnly();
        Permutation<string>.Choices = new List<string> { null, "", "Hello World" }.AsReadOnly();
    }

    public static IEnumerable<T> GetPermutations<T>()
    {
        if (Permutation<T>.Choices == null) {
            var props = typeof(T).GetProperties().Where(p => p.CanWrite);
            Permutation<T>.Choices = new List<T>(GeneratePermutations<T>(() => Activator.CreateInstance<T>(), props)).AsReadOnly();
        }
        return Permutation<T>.Choices;
    }

    private static IEnumerable GetPermutations(Type t) {
        var method = typeof(PermutationGenerator).GetMethod("GetPermutations", new Type[] {}).MakeGenericMethod(t);
        return (IEnumerable)(method.Invoke(null,new object[] {}));
    }

    private delegate T Generator<T>();

    private static IEnumerable<T> GeneratePermutations<T>(Generator<T> generator, IEnumerable<PropertyInfo> props)
    {
        if (!props.Any())
        {
            yield return generator();
        }
        else
        {
            var prop = props.First();
            var rest = props.Skip(1);

            foreach (var propVal in GetPermutations(prop.PropertyType))
            {
                Generator<T> gen = () =>
                {
                    var obj = generator();
                    prop.SetValue(obj, propVal, null);
                    return (T)obj;
                };
                foreach (var result in GeneratePermutations(gen, rest))
                {
                    yield return result;
                }
            }
        }
    }
}

answered Apr 6, 2009 at 19:53

kvb

55.2k2 gold badges94 silver badges133 bronze badges

5 Comments

Joel Coehoorn Over a year ago

2 problems with this: 1) It's not really the question he asked (it fits the question title, but not the content). 2) Recursive solution isn't really the best idea in this case. Read this: msdn.microsoft.com/en-us/library/aa302371.aspx

Martin Over a year ago

Wow! Amazing work! This is not perfect, but I have to say that I am impress. I want you in my team! :P

kvb Over a year ago

@Joel Coehorn - can you elaborate on 1? If you call PermutationGenerator.GetPermutations<Client>() as in the question, you'll get a set of Client objects with all combinations of the different properties set, as requested.

Martin Over a year ago

@kvb -- In GetPermutations<T>, how would you handle cases such as byte[]? There is no parameterless constructor for byte[].

kvb Over a year ago

You have two options: first of all, if there's a fixed set of byte[] values that you always want to use, set Permutation.Choices<byte[]> to that list in the static constructor. Otherwise, you'll need to extend the code a bit; how you do this will depend on what you want the code to do in that case.

mqp · Accepted Answer · 2009-04-06 19:14:01Z

1

Most non-trivial dynamically allocated objects -- like strings -- don't have a finite amount of different "permutations" they can be in. That string can be as long as you want until your RAM runs out.

So this is really a completely Sisyphean task, and there's no point going on with it as stated unless you put a lot more heavy restrictions on what kind of permutations you're looking for.

answered Apr 6, 2009 at 19:14

mqp

72.3k15 gold badges99 silver badges124 bronze badges

Comments

Stephanvs · Accepted Answer · 2009-04-06 19:15:11Z

1

You can have a look at PEX

http://research.microsoft.com/en-us/projects/pex/default.aspx

It's a whitebox test generation tool which integrates in Visual Studio.

answered Apr 6, 2009 at 19:15

Stephanvs

7317 silver badges19 bronze badges

Comments

GWLlosa · Accepted Answer · 2009-04-06 19:36:34Z

0

As many have said, generating all permutations is computationally infeasible for non-trivial classes. What I have had to do, and had great success with, is generating all permutations of a class for a specific range of inputs; i.e., given a class with properties A, B, and C, I'd like to generate all permutations of A=1, A=2, B=1, C=3, and C=4, resulting in:

A=1, B=1, C=3

A=2, B=1, C=3

A=1, B=1, C=4

A=2, B=1, C=4

This kind of thing can be accomplished with recursive algorithms or some really elegant LINQ queries. There's a fairly exhaustive piece on that here, but its a good amount of programming and it really helps if you're boned up on your Set Theory.

answered Apr 6, 2009 at 19:36

GWLlosa

24.6k18 gold badges83 silver badges119 bronze badges

Comments

Samuel · Accepted Answer · 2009-04-06 19:12:50Z

-1

That's like asking to move the Great Wall of China in 1 hour, into space. It cannot be done.

You would need to know what defines each permutation of every type, even types you didn't create, and that's impossible.

answered Apr 6, 2009 at 19:12

Samuel

38.5k11 gold badges88 silver badges87 bronze badges

2 Comments

Aziz Over a year ago

you can move the Great Wall of China into space in 1 hour ... if you have the resources :P

Samuel Over a year ago

Yeah, and you can technically do it using recursion and reflection, but that would be horrible to look at and slow. And the only use would be for testing, and I don't see how testing every possible permutation would be helpful.

Collectives™ on Stack Overflow

Generate all the possible permutations of a class

6 Answers 6

Comments

5 Comments

Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

5 Comments

Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related