-3

I'm trying to list all permutations of variables, where each variable has 2 alternatives which can not be in the same permutation.

Let's say we have 2 variables A and B but I need to use them with an Index as A1, A2 and B1, B2. To make it even more complicated, the "1" index can occur alone and is not allowed with another "1", the "2" index can not occur alone. So what I need would be:

  • A1
  • B1
  • A1 B2
  • B1 A2

Using 3 variables A1, A2, B1, B2, C1, C2:

  • A1
  • A1 B2
  • A1 C2
  • A1 B2 C2
  • B1
  • B1 A2
  • B1 C2
  • B1 A2 C2
  • C1
  • C1 A2
  • C1 B2
  • C1 A2 B2

And I would need it for n variables (n1, n2). I found this one, but it didn't really help me:permutations variable length, but it doesn't quite fit. Actually I don't have a clue at all at the moment how to handle this.

rene
  • 41,474
  • 78
  • 114
  • 152
Doedel
  • 1
  • 1
  • Why don't those other answer fit? Where were you stuck when you implemented that answer? – rene Oct 19 '18 at 06:21
  • we are not a coding service – jazb Oct 19 '18 at 06:24
  • my problem are the indexes, I dont know how to implement them in the other answer – Doedel Oct 19 '18 at 06:27
  • This would be an interesting question, however its very hard to understand – TheGeneral Oct 19 '18 at 06:35
  • So you choose a letter from the 1 list, and then remove that letter from the 2 list. Now the 2 list has (n-1) items that can be chosen 2^(n-1) different ways. This is clear from the 2nd example, where you have 4 permutations starting with A1, 4 with B1, and 4 with C1. The first example follows the same pattern if you switch B1 with A1 B2. In other words, this problem is the same as the linked question, but you need to remove one item from the list. – user3386109 Oct 19 '18 at 06:41
  • Thank you! Actually quite simple, but that would be a nice approach. And for the permutations of the "2" list I could use something similar to the linked answer. – Doedel Oct 19 '18 at 06:47

1 Answers1

0

I am not certain if i got your problem correctly but let me give it a try. For this specific set creation I took the approach to split the problem in first entries like A1and second entries like A2. I created the following algorithm:

  1. Create a List of all first entries according to input n (for n == 3 it would be {A1, B1, C1})

  2. Create a List of all second entries according to input n (for n == 3 it would be {A2, B2, C2})

  3. For each firstEntry like A1

    1. For each set in the powerset of second entries
    2. If there is no collision like A1 and A2
      1. Concatenate the set of e.g. {B2, C2} to create a concatenation like B2C2
      2. Add new item = firstEntry + concatenated set to list of my custom set
  4. Return custom set

For the implementation i used this for algorithm step 3.1. leading to the following implementation:

    private List<string> GetCustomPermutations(int count)
    {
        if(count < 1)
        {
            return new List<string>();
        }

        List<string> firstEntries = new List<string>();
        List<string> secondEntries = new List<string>();

        // Create list of firstEntries = {A1, B1, ...} and secondEntries = {A2, B2, ...} from count
        for (int i = 0; i < count; i++)
        {
            firstEntries.Add((char)('A' + i) + "1");
            secondEntries.Add((char)('A' + i) + "2");
        }

        // Get Powerset of second Entries
        string[][] FullPowerSet = FastPowerSet(secondEntries.ToArray());

        List<string> CustomSet = new List<string>();
        foreach (string firstEntry in firstEntries)
        {
            for (int i = 0; i < FullPowerSet.Length; i++)
            {
                // join the second array dimension to create the appended entry
                string appendedEntry = string.Join("", FullPowerSet[i]);

                // Avoid adding the firstentry char to the appended aswell
                if (appendedEntry.Contains(firstEntry[0]))
                {
                    continue;
                }
                CustomSet.Add(firstEntry + appendedEntry);
            }
        }
        return CustomSet;
    }

    // Create a powerset of every input array, see https://stackoverflow.com/questions/19890781/creating-a-power-set-of-a-sequence
    public static T[][] FastPowerSet<T>(T[] seq)
    {
        var powerSet = new T[1 << seq.Length][];
        powerSet[0] = new T[0]; // starting only with empty set
        for (int i = 0; i < seq.Length; i++)
        {
            var cur = seq[i];
            int count = 1 << i; // doubling list each time
            for (int j = 0; j < count; j++)
            {
                var source = powerSet[j];
                var destination = powerSet[count + j] = new T[source.Length + 1];
                for (int q = 0; q < source.Length; q++)
                    destination[q] = source[q];
                destination[source.Length] = cur;
            }
        }
        return powerSet;
    }
pfuhlert
  • 533
  • 4
  • 16