2

I've seen a lot of good questions about similar problems but not exactly what I'm looking for.

Given: a non-unique set of symbols (or characters)

(1, 1, 2, 3)

Expected: an output similar to this (the order isn't important, only the elements outputed)

1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211

I know I could pipe the permutation output into another algorithm similar to the uniq bash command but Im going to be using this on large strings and I want the "uniqueness" done on the fly not after the fact.

I imagine the easiest way to do something like this is to use a hash in the permutation algorithm with the permutations being the key but is there a smarter way to do this? Am I missing a cool trick here?

Edit: For better examples, I've provided two more

# given a set (1,1,1,2,3)
[1, 1, 1, 2, 3]
[1, 1, 1, 3, 2]
[1, 1, 2, 1, 3]
[1, 1, 2, 3, 1]
[1, 1, 3, 1, 2]
[1, 1, 3, 2, 1]
[1, 2, 1, 1, 3]
[1, 2, 1, 3, 1]
[1, 2, 3, 1, 1]
[1, 3, 1, 1, 2]
[1, 3, 1, 2, 1]
[1, 3, 2, 1, 1]
[2, 1, 1, 1, 3]
[2, 1, 1, 3, 1]
[2, 1, 3, 1, 1]
[2, 3, 1, 1, 1]
[3, 1, 1, 1, 2]
[3, 1, 1, 2, 1]
[3, 1, 2, 1, 1]
[3, 2, 1, 1, 1]

# given a set (1, 1, 2, 2, 3)
[1, 1, 2, 2, 3]
[1, 1, 2, 3, 2]
[1, 1, 3, 2, 2]
[1, 2, 1, 2, 3]
[1, 2, 1, 3, 2]
[1, 2, 2, 1, 3]
[1, 2, 2, 3, 1]
[1, 2, 3, 1, 2]
[1, 2, 3, 2, 1]
[1, 3, 1, 2, 2]
[1, 3, 2, 1, 2]
[1, 3, 2, 2, 1]
[2, 1, 1, 2, 3]
[2, 1, 1, 3, 2]
[2, 1, 2, 1, 3]
[2, 1, 2, 3, 1]
[2, 1, 3, 1, 2]
[2, 1, 3, 2, 1]
[2, 2, 1, 1, 3]
[2, 2, 1, 3, 1]
[2, 2, 3, 1, 1]
[2, 3, 1, 1, 2]
[2, 3, 1, 2, 1]
[2, 3, 2, 1, 1]
[3, 1, 1, 2, 2]
[3, 1, 2, 1, 2]
[3, 1, 2, 2, 1]
[3, 2, 1, 1, 2]
[3, 2, 1, 2, 1]
[3, 2, 2, 1, 1]
  • It would be nice to specify what you mean by "duplicate" and what is the max number of subsets you want generated as this would define the required algorithm better. – NoChance Apr 30 at 1:11
1

One possible way could be to first convert your string in a map of character to integers.

Then you would iterate over the keys of the map to select the next possible character.

#include <iostream>
#include <map>

std::map<char, size_t>  getCharacterMap(const std::string &s)
  {
  std::map<char, size_t> charactersCount;
  for(std::string::size_type i = 0; i < s.size(); ++i)
    ++charactersCount[s[i]];
  return charactersCount;
  }


void recursivePermutation(const std::string &partialPermutation, const std::map<char, size_t> &charCount)
  {
  if (charCount.empty())
    {
    std::cout << partialPermutation << std::endl;
    return;
    }
  for (std::map<char, size_t>::const_iterator it = charCount.begin(); it != charCount.end(); ++it)
    {
    char key = it->first;
    size_t count = it->second;
    std::string longerPartialPermutation = partialPermutation;
    longerPartialPermutation += key;
    std::map<char, size_t> reducedCount = charCount;
    if (count == 1)
      reducedCount.erase(reducedCount.find(key));
    else
       reducedCount[key]-=1;
    recursivePermutation(longerPartialPermutation, reducedCount);
    }

  }

void permutation(const std::string &s)
  {
  std::map<char, size_t> charCount = getCharacterMap(s);
  recursivePermutation("", charCount);
  }

int main()
  {
  permutation("1122");
  return 0;
  }
  • I'm not familiar with some of this syntax. This looks like c++ (std library, cout etc) but not the auto and arrow notation after the parameters. Has there been an update to the C++ syntax since I learned it in school? – triplethreat78 Apr 29 at 22:27
  • Im assuming the return type is now at the end of the parameters and auto denotes this or something? – triplethreat78 Apr 29 at 22:28
  • @DJTripleThreat the auto and trailing return type are indeed c++11/13/17 syntax, I removed them so that the code is easier to read for you. – Renaud M. Apr 30 at 4:27
  • Thanks man. An explanation is fine. No need to change it. I'm just a lowly Ruby guy anyway haha. – triplethreat78 Apr 30 at 5:16
  • Did you bother testing any of this code? There are a lot of errors in it. Not to mention you've got a wacky double quote thing going on when you're calling recursivePermutation towards the end of the code. Also the return line of your first method should be return characterCounts; with an s. – triplethreat78 Apr 30 at 5:47
4

This is exactly the example use of the C++ standard library function std::next_permutation, starting from sorted data.

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}

Has the output

aab
aba
baa

It doesn't include the duplicate cases with "swapped" as.

Adapting the possible implementation from the linked reference to another language shouldn't be too difficult, e.g. C#:

class PermutationExtensions {
    private static void Swap<T>(IList<T> list, int indexA, int indexB)
    {
        T tmp = list[indexA];
        list[indexA] = list[indexB];
        list[indexB] = tmp;
    }

    private static bool NextPermutation(IList<T> list)
    {
        if (list.Count() < 2) return false;
        int i = list.Count() - 1;

        while (true) {
            int i1 = i;
            if (list[--i] < list[i1]) {
                int i2 = list.Count();
                while (!(list[i] < list[--i2]))
                    ;
                Swap(list, i, i2);
                list.Reverse(i1, list.Count() - i1);
                return true;
            }
            if (i == 0) {
                list.Reverse();
                return false;
            }
        }
    }

    public static IEnumerable<IList<T>> Permutations(this IEnumerable<T> items)
    {
        IList<T> local = items.ToList();
        local.Sort();
        yield local.ToList(); // clone the list as we modify it in NextPermutation
        while (NextPermutation(local))
        {
            yield local.ToList();
        }
    }
}
0

This doesn't require any substantial data structure, if you don't want to use one.

You can use nested loops to generate matches (i.e. triple for three matches, quadruple for for).

Skip any matches where an index is being reused, e.g. skip when an outer loop's index is the same as an inner loops index.  That ensures the basic permutations.

The next requirement is to skip the duplicates caused by the duplicate elements in the input.  This can be done lexically (or numerically).  Track the last permutation accepted, and skip any new ones that have a lessor (or same) value.

Here's my sample in VBA/Excel:

Sub doit()
    Dim r As Range
    Set r = ActiveSheet.Cells
    n = 4
    s = "1123"
    Dim row As Integer
    Dim last As Integer
    Let last = 0
    Let row = 1
    For i = 1 To n
        ic = Mid(s, i, 1)
        For j = 1 To n
            If j <> i Then  'skip this index if it is in use by i
                jc = Mid(s, j, 1)
                For k = 1 To n
                    If k <> i And k <> j Then   'skip this index if it is in use by i or j
                        kc = Mid(s, k, 1)
                        For m = 1 To n
                            If m <> i And m <> j And m <> k Then
                                mc = Mid(s, m, 1)
                                v = ic & jc & kc & mc 'v is our candidate permutation
                                Dim x As Integer
                                Let x = Int(v)  'use value of string for greater than
                                If x > last Then
                                    Let r.Cells(row, 1).Value = v
                                    Let last = x
                                    Let row = row + 1 'move output to different row of worksheet
                                End If
                            End If
                        Next
                    End If
                Next
            End If
        Next
    Next
End Sub

(This version requires that the string you provide has its characters stored in increasing order.)

  • Thats a fair requirement and honestly, a good way to start the algorithm anyway since you're getting every unique combination of digits anyway. I'll give this a shot and see if it works for bigger cases. – triplethreat78 Apr 29 at 22:22
  • one could generalize this to use a data structure: an array holding the index positions, instead of scalars i, j, k... if you did all that then you wouldn't need to change the number of nested loops for different problem sets.. – Erik Eidt Apr 29 at 22:35
  • Yeah I was thinking about rolling my own in case I couldn't find a solution already. Mine would be an n-ary tree with with node having an array of unique symbols, once you ran out of a certain symbol (count == 0) it would no longer show up in child nodes and when you had to symbols left you can assume the path you traveled would be counted first and then just add the other symbol instead of making another node. This would be a leaf basically. – triplethreat78 Apr 29 at 22:42
  • It looks like I can't run this macro. Im running on Linux and use LibreOffice Calc, not Excel. Apparently, you can't migrate macros from one to the other without some modifications. Hopefully I can work this out. See this link (Range is not a valid data type in Calc I guess): forum.openoffice.org/en/forum/… – triplethreat78 Apr 29 at 22:54
  • yeah, sorry about that. you might transfer to java or C#... – Erik Eidt Apr 30 at 0:33
0

Another option to explore, maybe, is to use generative grammars, eg, for your (1, 1, 2, 2, 3) last example:

Word -> One One Two Two Three
      | One One Two Three Two
      | One One Three Two Two
      | ... (etc)

(where the alphabet also drives how many One's vs Two's vs Three's are allowed to appear on the right hand side)

One -> 1

Two -> 2

Three -> 3

Word being the grammar axiom, with the only non terminal productions - (where pipe "|" is the usual BNF symbol for alternatives) - and One, Two, Three being the only terminal productions of the respective 3 distinct classes of terminal symbols - 1, 2, 3.

Then the algorithm consists in,

1) preparing the One, Two, and Three set of productions (based on your alphabet)

2) preparing the Word set of production alternatives - ie, that "Word -> ... | ..." rule - based on known word length and on the permutations over the terminal ones that may appear on the right hand side (One, Two, Three), prior obtained in (1)

3) simply enumerating the Word productions obtained in (2) and applying them in sequence.

Your uniqueness requirement has thus basically been "reduced", so to speak, to that of the uniqueness of what (2), itself, can generate.

'Hth

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.