All geek questions in one place

Get great combinations of numbers using LINQ

The following code returns all the various combinations based on logic that are 1,2,3 = 3,2,1 = 2,3,1, so it returns only one instance of this set of numbers.

However, I want to change this logic so that it returns ALL instances of all sets of numbers.

What do I need to do for the LINQ query below "GetPowerSet" to make this happen?

    public void GetPowersets()
    {
        List<int> ints = new List<int>()
        {
            1,2,2,3,3
        };

        var results = GetPowerSet(ints);


        List<String> combinations = new List<String>();
        foreach (var result in results)
        {
            StringBuilder sb = new StringBuilder();
            foreach (var intValue in result.OrderBy(x => x))
            {
                sb.Append(intValue + ",");
            }
            combinations.Add(sb.ToString());
        }

        string c1 = string.Join("|", combinations.ToArray()).Replace(",|", "|");
        //c1 = "|1|2|1,2|2|1,2|2,2|1,2,2|3|1,3|2,3|1,2,3|2,3|1,2,3|2,2,3|1,2,2,3|3|1,3|2,3|1,2,3|2,3|1,2,3|2,2,3|1,2,2,3|3,3|1,3,3|2,3,3|1,2,3,3|2,3,3|1,2,3,3|2,2,3,3|1,2,2,3,3,"

    }

    public IEnumerable<IEnumerable<int>> GetPowerSet(List<int> list)
    {
        return from m in Enumerable.Range(0, 1 << list.Count)
                     select
                         from i in Enumerable.Range(0, list.Count)
                         where (m & (1 << i)) != 0
                         select list[i];
    }

This is the end result I'm trying to achieve: (no duplicate combination strings: duplicate = 3,2,1 and 3,2,1 are the same thing, but 1,2,3 and 3,2,1 are NOT one and the same, and both should be the end result)

1
2
3
1,2
1,3
2,1
2,3
2,2
3,1
3,2
3,3
1,2,3
1,2,2
1,3,2
1,3,3
2,1,3
2,1,2
2,3,1
2,3,2
2,3,3
2,2,1
2,2,3
3,1,2
3,1,3
3,2,1
3,2,2
3,2,3
3,3,1
3,3,2
1,2,3,2
1,2,3,3
1,2,2,3
1,3,2,2
1,3,2,3
1,3,3,2
2,1,3,2
2,1,3,3
2,1,2,3
2,3,1,2
2,3,1,3
2,3,2,1
2,3,2,3
2,3,3,1
2,3,3,2
2,2,1,3
2,2,3,1
2,2,3,3
3,1,2,2
3,1,2,3
3,1,3,2
3,2,1,2
3,2,1,3
3,2,2,1
3,2,2,3
3,2,3,1
3,2,3,2
3,3,1,2
3,3,2,1
3,3,2,2
1,2,3,2,3
1,2,3,3,2
1,2,2,3,3
1,3,2,2,3
1,3,2,3,2
1,3,3,2,2
2,1,3,2,3
2,1,3,3,2
2,1,2,3,3
2,3,1,2,3
2,3,1,3,2
2,3,2,1,3
2,3,2,3,1
2,3,3,1,2
2,3,3,2,1
2,2,1,3,3
2,2,3,1,3
2,2,3,3,1
3,1,2,2,3
3,1,2,3,2
3,1,3,2,2
3,2,1,2,3
3,2,1,3,2
3,2,2,1,3
3,2,2,3,1
3,2,3,1,2
3,2,3,2,1
3,3,1,2,2
3,3,2,1,2
3,3,2,2,1

"foreach" , " ", ( , LINQ ) . , , , . . , .

public List<List<int>> GetAllCombinationsOfAllSizes(List<int> ints)
{
    List<List<int>> returnResult = new List<List<int>>();

    var distinctInts = ints.Distinct().ToList();
    for (int j = 0; j < distinctInts.Count(); j++)
    {
        var number = distinctInts[j];

        var newList = new List<int>();
        newList.Add(number);
        returnResult.Add(newList);

        var listMinusOneObject = ints.Select(x => x).ToList();
        listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

        if (listMinusOneObject.Count() > 0)
        {
            _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
        }
    }

    return returnResult;
}
public void _GetAllCombinationsOfAllSizes(List<int> ints, List<int> growingList, ref List<List<int>> returnResult)
{
    var distinctInts = ints.Distinct().ToList();
    for (int j = 0; j < distinctInts.Count(); j++)
    {
        var number = distinctInts[j];

        var newList = growingList.ToList();
        newList.Add(number);
        returnResult.Add(newList);

        var listMinusOneObject = ints.Select(x => x).ToList();
        listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

        if (listMinusOneObject.Count() > 0)
        {
            _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
        }
    }

}

ANSWER : , , LINQ # , , , "foreach" , ?

+4
3

NEW UPDATE ( , , OP-, )

static IEnumerable<int[]> EnumeratePermutations2(int[] ints)
{
    Dictionary<int, int> intCounts = ints.GroupBy(n => n)
                                         .ToDictionary(g => g.Key, g => g.Count());
    int[] distincts = intCounts.Keys.ToArray();
    foreach (int[] permutation in EnumeratePermutations2(new int[0], intCounts, distincts))
        yield return permutation;
}

static IEnumerable<int[]> EnumeratePermutations2(int[] prefix, Dictionary<int, int> intCounts, int[] distincts)
{
    foreach (int n in distincts)
    {
        int[] newPrefix = new int[prefix.Length + 1];
        Array.Copy(prefix, newPrefix, prefix.Length);
        newPrefix[prefix.Length] = n;
        yield return newPrefix;
        intCounts[n]--;
        int[] newDistincts = intCounts[n] > 0
                             ? distincts
                             : distincts.Where(x => x != n).ToArray();
        foreach (int[] permutation in EnumeratePermutations2(newPrefix, intCounts, newDistincts))
            yield return permutation;
        intCounts[n]++;
    }
}
+2

.

, . . , 89 .

64 , , 2 ^ List.Count() = 2 ^ 6 = 64

, , . , , . , , , : http://www.codeproject.com/Articles/23391/Set-Collections-for-C

, , - TPL Library, . : http://msdn.microsoft.com/en-us/library/dd460717 (v = vs .110).aspx

190 . 1,5 .

void Main()
{
    var setList = new List<int>() {1,1,2,3,3,3};
    var setSize = setList.Count();

    var basePowerSet = PowerSet.Generate(setList);
    var results = PowerSet.PS;


    // Results generated in 1 Minute 23 seconds with no errors.

    var sortedSets = new SortedSet<string>();

    foreach( var item in results)
    {
        sortedSets.Add(item.ToString2());
    }

    foreach( var item in sortedSets)
    {
        Console.WriteLine(item);
    }   


}

PowerSet

public static class PowerSet
{
    // List with no Exact Duplicates but with Permutations
    public static List<List<int>> PS =  new List<List<int>>();


    // This Method Generates the power set with No Exact Duplicates
    // and stores the values into the Property PS.
    public static List<List<int>> Generate(List<int> setList)
    {
        // Generate Base Data to use for final results
        var setSize = setList.Count();
        var basePowerSet = from m in Enumerable.Range(0, 1 << setSize)
                select
                    from i in Enumerable.Range(0, setSize)
                    where (m & (1 << i)) != 0 
                    select setList[i];

        // Temporary Result Set with Duplicates
        var results = new List<List<int>>();

        // Step thru each set and generate list of Permutations for each
        // Power Set generated above.
        foreach( var item in basePowerSet )
        {
            var size = item.Count();
            var positions = from m in Enumerable.Range(0, size)
                select m;

            var lItem = item.ToList();  

            // If the set has 2 or more elements in the set then generate Permutations
            switch(size)
            {
                case 0:
                case 1:
                    break;
                default:

                    // Permutations generated from Linq Extension defined
                    // in Method Permute()
                    var posList = positions.Permute().ToList();

                    // remove first item which is a duplicate.
                    posList.RemoveAt(0);

                    // Generate new Lists based on all possiable
                    // combinations of the data in the set.
                    var x = new List<List<int>>();
                    foreach(var p in posList)
                    {   
                        var y = new List<int>();
                        foreach(var v in p)
                        {
                            //v.Dump("xxxx");
                            y.Add(lItem[v]);
                        }

                        x.Add(y);

                        // Add New Permutation but
                        // Do not add a duplicate set.
                        AddNonDuplicate(x);
                    }                                       
                    break;
            }

            // Add to Temp Results;
            results.Add(item.ToList());

            // Remove Duplicates
            AddNonDuplicate(results);
        }

        return results;
    }


    // Custom Method used to compare values in a set to the
    // Final Result Set named PS.
    public static void AddNonDuplicate(List<List<int>> list )
    {
        //list.Dump();
        if(list.Count() == 0)
            return;

        foreach(var item in list)
        {
            bool found = false;
            var mySize = PS.Count();
            if(mySize <= 0)
                PS.Add(item);
            else
                foreach(var psItem in PS)
                {
                    if( item.ToString2() == psItem.ToString2() )
                        found = true;
                }

            if(!found)
                PS.Add(item);
        }
    }

}


// My Extension Methods
public static class MyExt
{

    public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> list)
    {
        if (list.Count() == 1)
            return new List<IEnumerable<T>> { list };
        return list
            .Select((a, i1) => 
                        Permute(list.Where((b, i2) => i2 != i1))
                    .Select(b => (new List<T> { a }).Union(b)))
            .SelectMany(c => c);
    }


    public static string ToString2<T>(this List<T> list)
    {
        StringBuilder results = new StringBuilder("{ ");
        var size = list.Count();
        var pos = 1;

        foreach( var i in list )
        {
            results.Append(i.ToString());
            if(pos++!=size)
                results.Append(", ");
        }

        results.Append(" }");               
        return results.ToString().Trim(',');
    }
}


{  }
{ 1 }
{ 1, 1 }
{ 1, 1, 2 }
{ 1, 1, 2, 3 }
{ 1, 1, 2, 3, 3 }
{ 1, 1, 2, 3, 3, 3 }
{ 1, 1, 3 }
{ 1, 1, 3, 2 }
{ 1, 1, 3, 2, 3 }
{ 1, 1, 3, 2, 3, 3 }
{ 1, 1, 3, 3 }
{ 1, 1, 3, 3, 2 }
{ 1, 1, 3, 3, 2, 3 }
{ 1, 1, 3, 3, 3 }
{ 1, 1, 3, 3, 3, 2 }
{ 1, 2 }
{ 1, 2, 1 }
{ 1, 2, 1, 3 }
{ 1, 2, 1, 3, 3 }
{ 1, 2, 1, 3, 3, 3 }
{ 1, 2, 3 }
{ 1, 2, 3, 1 }
{ 1, 2, 3, 1, 3 }
{ 1, 2, 3, 1, 3, 3 }
{ 1, 2, 3, 3 }
{ 1, 2, 3, 3, 1 }
{ 1, 2, 3, 3, 1, 3 }
{ 1, 2, 3, 3, 3 }
{ 1, 2, 3, 3, 3, 1 }
{ 1, 3 }
{ 1, 3, 1 }
{ 1, 3, 1, 2 }
{ 1, 3, 1, 2, 3 }
{ 1, 3, 1, 2, 3, 3 }
{ 1, 3, 1, 3 }
{ 1, 3, 1, 3, 2 }
{ 1, 3, 1, 3, 2, 3 }
{ 1, 3, 1, 3, 3 }
{ 1, 3, 1, 3, 3, 2 }
{ 1, 3, 2 }
{ 1, 3, 2, 1 }
{ 1, 3, 2, 1, 3 }
{ 1, 3, 2, 1, 3, 3 }
{ 1, 3, 2, 3 }
{ 1, 3, 2, 3, 1 }
{ 1, 3, 2, 3, 1, 3 }
{ 1, 3, 2, 3, 3 }
{ 1, 3, 2, 3, 3, 1 }
{ 1, 3, 3 }
{ 1, 3, 3, 1 }
{ 1, 3, 3, 1, 2 }
{ 1, 3, 3, 1, 2, 3 }
{ 1, 3, 3, 1, 3 }
{ 1, 3, 3, 1, 3, 2 }
{ 1, 3, 3, 2 }
{ 1, 3, 3, 2, 1 }
{ 1, 3, 3, 2, 1, 3 }
{ 1, 3, 3, 2, 3 }
{ 1, 3, 3, 2, 3, 1 }
{ 1, 3, 3, 3 }
{ 1, 3, 3, 3, 1 }
{ 1, 3, 3, 3, 1, 2 }
{ 1, 3, 3, 3, 2 }
{ 1, 3, 3, 3, 2, 1 }
{ 2 }
{ 2, 1 }
{ 2, 1, 1 }
{ 2, 1, 1, 3 }
{ 2, 1, 1, 3, 3 }
{ 2, 1, 1, 3, 3, 3 }
{ 2, 1, 3 }
{ 2, 1, 3, 1 }
{ 2, 1, 3, 1, 3 }
{ 2, 1, 3, 1, 3, 3 }
{ 2, 1, 3, 3 }
{ 2, 1, 3, 3, 1 }
{ 2, 1, 3, 3, 1, 3 }
{ 2, 1, 3, 3, 3 }
{ 2, 1, 3, 3, 3, 1 }
{ 2, 3 }
{ 2, 3, 1 }
{ 2, 3, 1, 1 }
{ 2, 3, 1, 1, 3 }
{ 2, 3, 1, 1, 3, 3 }
{ 2, 3, 1, 3 }
{ 2, 3, 1, 3, 1 }
{ 2, 3, 1, 3, 1, 3 }
{ 2, 3, 1, 3, 3 }
{ 2, 3, 1, 3, 3, 1 }
{ 2, 3, 3 }
{ 2, 3, 3, 1 }
{ 2, 3, 3, 1, 1 }
{ 2, 3, 3, 1, 1, 3 }
{ 2, 3, 3, 1, 3 }
{ 2, 3, 3, 1, 3, 1 }
{ 2, 3, 3, 3 }
{ 2, 3, 3, 3, 1 }
{ 2, 3, 3, 3, 1, 1 }
{ 3 }
{ 3, 1 }
{ 3, 1, 1 }
{ 3, 1, 1, 2 }
{ 3, 1, 1, 2, 3 }
{ 3, 1, 1, 2, 3, 3 }
{ 3, 1, 1, 3 }
{ 3, 1, 1, 3, 2 }
{ 3, 1, 1, 3, 2, 3 }
{ 3, 1, 1, 3, 3 }
{ 3, 1, 1, 3, 3, 2 }
{ 3, 1, 2 }
{ 3, 1, 2, 1 }
{ 3, 1, 2, 1, 3 }
{ 3, 1, 2, 1, 3, 3 }
{ 3, 1, 2, 3 }
{ 3, 1, 2, 3, 1 }
{ 3, 1, 2, 3, 1, 3 }
{ 3, 1, 2, 3, 3 }
{ 3, 1, 2, 3, 3, 1 }
{ 3, 1, 3 }
{ 3, 1, 3, 1 }
{ 3, 1, 3, 1, 2 }
{ 3, 1, 3, 1, 2, 3 }
{ 3, 1, 3, 1, 3 }
{ 3, 1, 3, 1, 3, 2 }
{ 3, 1, 3, 2 }
{ 3, 1, 3, 2, 1 }
{ 3, 1, 3, 2, 1, 3 }
{ 3, 1, 3, 2, 3 }
{ 3, 1, 3, 2, 3, 1 }
{ 3, 1, 3, 3 }
{ 3, 1, 3, 3, 1 }
{ 3, 1, 3, 3, 1, 2 }
{ 3, 1, 3, 3, 2 }
{ 3, 1, 3, 3, 2, 1 }
{ 3, 2 }
{ 3, 2, 1 }
{ 3, 2, 1, 1 }
{ 3, 2, 1, 1, 3 }
{ 3, 2, 1, 1, 3, 3 }
{ 3, 2, 1, 3 }
{ 3, 2, 1, 3, 1 }
{ 3, 2, 1, 3, 1, 3 }
{ 3, 2, 1, 3, 3 }
{ 3, 2, 1, 3, 3, 1 }
{ 3, 2, 3 }
{ 3, 2, 3, 1 }
{ 3, 2, 3, 1, 1 }
{ 3, 2, 3, 1, 1, 3 }
{ 3, 2, 3, 1, 3 }
{ 3, 2, 3, 1, 3, 1 }
{ 3, 2, 3, 3 }
{ 3, 2, 3, 3, 1 }
{ 3, 2, 3, 3, 1, 1 }
{ 3, 3 }
{ 3, 3, 1 }
{ 3, 3, 1, 1 }
{ 3, 3, 1, 1, 2 }
{ 3, 3, 1, 1, 2, 3 }
{ 3, 3, 1, 1, 3 }
{ 3, 3, 1, 1, 3, 2 }
{ 3, 3, 1, 2 }
{ 3, 3, 1, 2, 1 }
{ 3, 3, 1, 2, 1, 3 }
{ 3, 3, 1, 2, 3 }
{ 3, 3, 1, 2, 3, 1 }
{ 3, 3, 1, 3 }
{ 3, 3, 1, 3, 1 }
{ 3, 3, 1, 3, 1, 2 }
{ 3, 3, 1, 3, 2 }
{ 3, 3, 1, 3, 2, 1 }
{ 3, 3, 2 }
{ 3, 3, 2, 1 }
{ 3, 3, 2, 1, 1 }
{ 3, 3, 2, 1, 1, 3 }
{ 3, 3, 2, 1, 3 }
{ 3, 3, 2, 1, 3, 1 }
{ 3, 3, 2, 3 }
{ 3, 3, 2, 3, 1 }
{ 3, 3, 2, 3, 1, 1 }
{ 3, 3, 3 }
{ 3, 3, 3, 1 }
{ 3, 3, 3, 1, 1 }
{ 3, 3, 3, 1, 1, 2 }
{ 3, 3, 3, 1, 2 }
{ 3, 3, 3, 1, 2, 1 }
{ 3, 3, 3, 2 }
{ 3, 3, 3, 2, 1 }
{ 3, 3, 3, 2, 1, 1 }
0

GetPowerSet, SetComparer .

public class SetComparer : IEqualityComparer<IEnumerable<int>>
{
    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        return Object.ReferenceEquals(x, y) || (x != null && y != null && x.SequenceEqual(y));
    }

    public int GetHashCode(IEnumerable<int> set)
    {
        if (set == null) return 0;

        //if you only want one of these 1,2,3 vs 3,2,1
        //plug .OrderBy(x => x) before the Aggregate
        return set.Aggregate(19, (s,i) => s * 31 + i);
    }
}

.Distinct(new SetComparer()) GetPowerSet select.

0

Source: https://habr.com/ru/post/1542361/

More articles:


All Articles