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

Answer 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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;
                }
            }
        }
    }
}