0

So I've searched around and honestly can't find a solution.

I'm completely lost, having one of those days.

Let's say I have this set

string[] arr = { "N", "N", "N", "N", "O", "O", "O", "O" };

I want to find all possible unique permutations, where there are never more "O"s than "N"s preceding it.

I.e If at index [2], 1 "N" and 1 "O" have been already come before it, then arr[2] must hold an "N". ["N","O","N",...]

I want to write a function that can output a 2D array of all permutations that follow these rules for any sized set.

Any help would be greatly appreciated.

MattyB
  • 19
  • 1
  • 6
  • 1
    How big can the input be? Given that there are only two types of input at any point, I'd be tempted to just treat each potential permutation as an integer (considering it in binary with N=1 and O=0 or vice versa) and just run through all integers in the possible range to see whether they fit - but that will only scale so far. – Jon Skeet Sep 10 '18 at 08:42
  • @DaisyShipton this was one of my first thoughts, but the more I thought about it the more complicated it seemed. What pattern of loops/iterations would provide me with a definitive set of unique permutations? I swear my brain's gone to mush today. – MattyB Sep 10 '18 at 08:47
  • 1
    If there is a duplication it's not a "set" – Vladi Pavelka Sep 10 '18 at 08:48
  • @VladiPavelka Sorry for using the wrong terminology, i guess i just meant an array/group. Any help would be greatly appreciated – MattyB Sep 10 '18 at 08:51
  • 1
    @MattyB sounds like an interview question : ) I'll give it a try – Vladi Pavelka Sep 10 '18 at 08:56
  • Perhaps https://stackoverflow.com/a/13891349/468973 can help. – Magnus Sep 10 '18 at 09:01
  • If you regard every possible permutation as an integer, looping through them all is trivial: you just use a normal `for` loop from 0 to the highest value (e.g. 255 in the example, as there are 8 bits per value). You'd then validate that it has the right number of bits set, and their positions. – Jon Skeet Sep 10 '18 at 09:45
  • Very unfortunate question close : / I was in the middle of writing a 2 page-downs explanation of different versions of solution algo and its algorithmic complexities – Vladi Pavelka Sep 10 '18 at 09:52
  • @Vladi Pavelka This is well-known problem with numerous descriptions and analysis (Catalan numbers). If you think you have new useful information, I can try to reopen (not sure it is possible) – MBo Sep 10 '18 at 09:56
  • https://pastebin.com/ypQ9Erwm – Vladi Pavelka Sep 10 '18 at 09:57
  • @MBo I was just disappointed I got cut off, but it's ok : ) – Vladi Pavelka Sep 10 '18 at 10:03
  • @MattyB check the pastebin link – Vladi Pavelka Sep 10 '18 at 11:06
  • @VladiPavelka Thanks! I'll look over it now. Thanks for taking the time to go through this. – MattyB Sep 12 '18 at 03:30
  • @MattyB welcome! : ) – Vladi Pavelka Sep 12 '18 at 15:40

0 Answers0