5

I want to get all the possible permutations of two different elements grouped by four without repeating the output but repeating elements (obviously you need to repeat elements to make combinations of 4 with only 2 elements).

So, some things I've tried:

sorted(list(map(lambda x: "".join(x), list(permutations('AB', 4)))))

returns an empty list. So I tried this instead:

sorted(list(map(lambda x: "".join(x), list(permutations('AABB', 4)))))

And it is closed to the output I expect, but full of redundant items, just a few of them:

['AABB','AABB','AABB','AABB','ABAB','ABAB','ABAB',...

What I expected to get is actually:

['AABB','ABAB','ABBA','BAAB','BABA','BBAA']

I tried also combinations() and product() instead of permutations() without success, but maybe my arguments weren't fit to the problem.

Any ideas?

Thanks a lot in advance!

PS. As pointed out by Antoine, there's a workaround using a set instead of a list, like:

sorted(list(map(lambda x: "".join(x), set(permutations('AABB', 4)))))

That gives the expected output, still it is generating all the repetitions anyway but just happen to be filtered out because sets cannot have repeated element, so it's probably not the most efficient way to do it.

Fran Marzoa
  • 4,293
  • 1
  • 37
  • 53
  • 2
    Making it a set would remove the duplicated. There is probably a more efficient way to do it though! – Antoine Boisier-Michaud Jun 09 '17 at 13:33
  • Thanks Antoine, I've right now trying that one by pure chance, but as you say that's a bit inefficient because it still generates all the duplicate stuff. – Fran Marzoa Jun 09 '17 at 13:34
  • 1
    Hm, @AntoineBoisier-Michaud's comment seems to have got in about 10 seconds quicker. I didn't see it when I posted the answer and in my defence the answer takes a lot longer to type out :-) – e4c5 Jun 09 '17 at 13:39
  • 1
    Why is *AAAB* not in the list of your expected results? – guidot Jun 09 '17 at 13:39
  • 1
    We have two As on the original set, so we cannot have three of them on the output. – Fran Marzoa Jun 09 '17 at 13:40
  • @Fran I also saw this in the code, but no supporting information in the problem description as well as in the original attempt. – guidot Jun 09 '17 at 13:41
  • 1
    Haha, no worries, @e4c5 ! I knew it wasn't the most efficient way, so I wrote it very quickly. – Antoine Boisier-Michaud Jun 09 '17 at 13:44
  • @guidot "permutations of two different elements" should be clear enough, I think. – Fran Marzoa Jun 09 '17 at 13:45
  • 1
    @Fran do you always have a set of 4 with 2 elements? Which mean always AABB or you can have something like ABCD? – Loïc Faure-Lacroix Jun 09 '17 at 13:49
  • Here's a similar question: [permutations with unique values](https://stackoverflow.com/questions/6284396/permutations-with-unique-values) – user2314737 Jun 09 '17 at 13:49
  • @LoïcFaure-Lacroix nah, that's only an example, you could have ABCD... up to Z and need to generate permutations of up to 25 elements, which by the way I've tried this way too and ended up killing the Python process because it was hogging all my laptop resources... – Fran Marzoa Jun 09 '17 at 13:53
  • I'm not sure it is a duplicate. In my opinion the problem is not described with sufficient precision to judge that. Trimmed down examples reach their limit here. I initially thought, the problem was, to form the words of a given length over a smaller alphabet but additional unspecified restrictions seem to exist about which letters can and must be repeated how often. – guidot Jun 09 '17 at 15:06

1 Answers1

5

Well you can use a set instead of a list and get the desired result

sorted(set(map(lambda x: "".join(x), list(permutations('AABB', 4)))))

But be warned that this may not work very well for very large number of elements in the bag. It doesn't scale

gives 

['AABB', 'ABAB', 'ABBA', 'BAAB', 'BABA', 'BBAA']

Slightly more perfomant perhaps

sorted(map(lambda x: "".join(x), set(permutations('AABB', 4))))

The permutations equivalent python code is listed here: https://docs.python.org/2/library/itertools.html#itertools.permutations

The original code is implemented in C so it would run faster. In the end doing permutations of large numbers of items simply does not scale whether or not you leave out duplicates.

e4c5
  • 52,766
  • 11
  • 101
  • 134
  • 2
    I've edited my question adding this as I told Antoine. It maybe an acceptable solution, still the optimal wouldn't need to generate all those repetitions. – Fran Marzoa Jun 09 '17 at 13:38
  • 1
    Even without using the set or the list. permutations doesn't scale at all. The number of possible elements can be calculted using nPr and substituing a few values will show you that the number of elements that needs to be processed grows really fast – e4c5 Jun 09 '17 at 13:40
  • I use scipy.special.binom to get the number of permutations, but I need this too to have those actual combinations available. It's for comparing the output of a function on a test case, so performance is not critical. Still, I've published this question just a few minutes ago, so I'll wait for others to provide answers before accepting one if you don't mind. Maybe someone else has a better idea. Otherwise I'll accept yours. – Fran Marzoa Jun 09 '17 at 13:50