6 Replies - 311 Views - Last Post: 01 June 2019 - 09:56 AM Rate Topic: -----

#1 RushabhVerma   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 8
  • Joined: 23-April 19

C# Permutate a set of strings given n and given the maximum array len.

Posted 22 May 2019 - 10:32 PM

How can you permutate the set of strings based on the set length, I have lets say 50 values in an array and only want to combine 24 values that is comma delimited Examples: (string1,string2,string3) but without ever repeating the combinations and the order. I have this code below.
class Program
{
    static void Main(string[] args)
    {
        //var values1 = new[] { 1, 2, 3, 4, 5 };

        //foreach (var permutation in values1.GetPermutations())
        //{
        //    Console.WriteLine(string.Join(", ", permutation));
        //}

        var values2 = new[] { "asd", "das", "sad", "q1we", "asd" };

        foreach (var permutation in values2.GetPermutations())
        {
            Console.WriteLine(string.Join(",", permutation));
        }

        Console.ReadLine();
    }
}

public static class SomeExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
    {
        var array = enumerable as T[] ?? enumerable.ToArray();

        var factorials = Enumerable.Range(0, array.Length + 1)
            .Select(Factorial)
            .ToArray();

        for (var i = 0L; i < factorials[array.Length]; i++)
        {
            var sequence = GenerateSequence(i, array.Length - 1, factorials);

            yield return GeneratePermutation(array, sequence);
        }
    }

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
    {
        var clone = (T[])array.Clone();

        for (int i = 0; i < clone.Length - 1; i++)
        {
            Swap(ref clone[i], ref clone[i + sequence[i]]);
        }

        return clone;
    }

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
    {
        var sequence = new int[size];

        for (var j = 0; j < sequence.Length; j++)
        {
            var facto = factorials[sequence.Length - j];

            sequence[j] = (int)(number / facto);
            number = (int)(number % facto);
        }

        return sequence;
    }

    static void Swap<T>(ref T a, ref T B)/>/>
    {
        T temp = a;
        a = b;
        b = temp;
    }

    private static long Factorial(int n)
    {
        long result = n;

        for (int i = 1; i < n; i++)
        {
            result = result * i;
        }

        return result;
    }
}
:code:

How can I be able to combine an array of string (24 values) into 100 rows of unique combination? Can you please explain how and whats the best way on how to do it?

This post has been edited by modi123_1: 23 May 2019 - 12:19 AM
Reason for edit:: In the future please use the [code] tag button in the editor


Is This A Good Question/Topic? 0
  • +

Replies To: C# Permutate a set of strings given n and given the maximum array len.

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6913
  • View blog
  • Posts: 23,492
  • Joined: 05-May 12

Re: C# Permutate a set of strings given n and given the maximum array len.

Posted 23 May 2019 - 04:57 AM

Are you looking for combinations, or permutations? Do you just care about the total count, or do you need the actual different arrangements/groupings?
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6913
  • View blog
  • Posts: 23,492
  • Joined: 05-May 12

Re: C# Permutate a set of strings given n and given the maximum array len.

Posted 23 May 2019 - 06:35 PM

Also posted on SO.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6913
  • View blog
  • Posts: 23,492
  • Joined: 05-May 12

Re: C# Permutate a set of strings given n and given the maximum array len.

Posted 23 May 2019 - 08:30 PM

After viewing the code of the currently accepted answer on SO, I have lost a lot of faith in SO's typical high standards for accepted answers.
Was This Post Helpful? 0
  • +
  • -

#5 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6913
  • View blog
  • Posts: 23,492
  • Joined: 05-May 12

Re: C# Permutate a set of strings given n and given the maximum array len.

Posted 01 June 2019 - 08:47 AM

I couldn't take it anymore last night. I posted a response on SO with a more deterministic generation of permutations rather than the proposed use of a randomizer that was accepted as the answer.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12605
  • View blog
  • Posts: 45,742
  • Joined: 27-December 08

Re: C# Permutate a set of strings given n and given the maximum array len.

Posted 01 June 2019 - 09:46 AM

@Skydiver- Perhaps it's worth sharing that code on DIC as well, just in case the SO thread gets deleted down the road. :)
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6913
  • View blog
  • Posts: 23,492
  • Joined: 05-May 12

Re: C# Permutate a set of strings given n and given the maximum array len.

Posted 01 June 2019 - 09:56 AM

From my SO response:

I propose the use of more deterministic permutation generator. Couple this with existing LINQ extension methods like Select(), Distinct() and Take() and you've got what you need:
var results = values2.Permutations(24)
                     .Select(p => String.Join(",", p))
                     .Distinct()
                     .Take(100);
foreach (var permutation in results)
    Console.WriteLine(permutation);


where Permutations() is implemented as an extension method. The number 24 here indicates how many items should be in each permutation. It is the k in nPk.

The Select() call creates a string string with all the items for the particular permutation.

The Distinct() call makes sure that we only end up with unique strings.

The Take() call limits the number of strings that we collect.

Here is a naive implementation using recursion to generate the permutations:
public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> source, int k)
{
    if (k < 0)
        throw new ArgumentOutOfRangeException(nameof(k), "May not be negative");

    var items = source.ToArray();
    if (k > items.Length)
        throw new ArgumentOutOfRangeException(nameof(k), "May not be bigger than the number of items in source");

    var buffer = new ArraySegment<T>(items, 0, k);
    return Permute(0);

    IEnumerable<T[]> Permute(int depth)
    {
        if (depth == k)
        {
            yield return buffer.ToArray();
            yield break;
        }

        for (int i = depth; i < items.Length; i++)
        {
            Swap(depth, i);
            foreach (var permutation in Permute(depth + 1))
                yield return permutation;
            Swap(depth, i);
        }
    }

    void Swap(int a, int b )
    {
        if (a != b )
        {
            T t = items[a];
            items[a] = items[b];
            items[b] = t;
        }
    }
}


I leave it to you to replace the implementation with the algorithm of your choice.
Was This Post Helpful? 2
  • +
  • -

Page 1 of 1