-2

So I've read this question about generation of permutations the fastest and I am probably going to use the Heap's Algorithm answer from Eric Ouellet, but what I want to do is only use the first N numbers of each permutation. Kind of like combinations but order matters. So Permutate 25 Take 10 is what I would say. If I was doing this for Permutate 3 Take 2, I would end up with

{1,2},{2,1},{3,2},{2,3},{1,3},{3,1}

I know if your Permutate length - choose > 1, you will end up with duplicates and I guess I will just ignore them while iterating through the results.

But to do this for my Permutate 25 Take 10, do you have to do the entire permutation of 25, then post process each permutation to return the first 10 items, or can Heap's (or something) be written in a manner to have the same cost as permutating 10 items? Any sample code would be great, preferably in C#, but I'm sure I could translate it from whatever.

Terry
  • 1,951
  • 2
  • 26
  • 45
  • If you write the code that gets a single permutation as an iterator then you can call `Take` on the result and it will only execute the relevant code as many times as you take values from the result. You could then call `Distinct` on the list of partial permutations to exclude duplicates. – John May 26 '22 at 04:10
  • I think that takes the first Take() permutations vs the first N elements of *each* permutation, right? – Terry May 26 '22 at 04:12
  • If you implement the code that gets the entire list of permutations and call `Take` on that then that will get a certain number of permutations. Is that what I said to do though? No, it isn't. I SPECIFICALY referred to *"the code that gets a single permutation"*. I haven't followed the link you provided, so I'm not sure how easy that would be or even whether it's possible, but that is what I said. – John May 26 '22 at 04:16
  • 1
    Possible dupe (although the code is in C): https://stackoverflow.com/q/51287171/1566221 – rici May 26 '22 at 04:39
  • Terry, consider adding to your question to require that answers be backed up with facts, timings or other proofs so as to avoid opinionated-answers. Good Luck! – MickyD May 26 '22 at 04:39
  • @mickyD: the question and answer in the link I suggested are backed up with facts and timings. – rici May 26 '22 at 04:40
  • As for the downvotes, it looks like you just posted on a bad day because I've been told many times that such questions are allowed even if there is no code. +1 regardless. – MickyD May 26 '22 at 04:41
  • @rici ooh! Nice find! Can always depend on the c/c++ crowd to do the right thing for this type of thing. ;) OP's question though is C#. But still, might be useful – MickyD May 26 '22 at 04:43
  • Although it's possible to generate permutation prefixes quite rapidly --a few nanoseconds per permutation-- you will probably want to do something with the permutations, which is likely to take a lot more time than generating them. Also, your 25 Take 10 involves generating 11,861,676,288,000 permutations. That's practical, since it's "only" a CPU-day of processing time, assuming what you do takes not much longer than the generation. But you'll probably want a parallelised version, assuming you have enough CPUs to throw at the problem. – rici May 26 '22 at 04:51
  • @MickyD: It really shouldn't be much of a challenge to convert C to C#. It's not C++. – rici May 26 '22 at 04:52
  • @rici agreed. Depending on how far the OP wants to go, I'd be inclined to leave the C code where it is, place it in a c++/CLI native-CLR hybrid project with a very simple managed wrapper that exposes a single method that is called once by the C# project. Do the conversions inside the hybrid if any only at the beginning and end of the call. – MickyD May 26 '22 at 05:05
  • @rici I read over your link. Tbh this type of stuff is so far out of my comfort zone. But from your comment you are saying 25 Take 10 is NOT the same cost as 10 Take 10 right? – Terry May 26 '22 at 05:08
  • 1
    @terry: that's clear, no? There are 25 different possibilities for each element in 25 take 10, and only 10 possibilities in 10 take 10. 10 take 10 is exactly 10!, but 25 take 10 is 25C10 * 10!, where C is the binomial coefficient, nCk = n!/(k! * (n-k)!). So n Take k = nCk * k! = n!/(n-k)!. 25 Take 10 is 25*24*23*22*21*20*19*18*17*16, which is a lot more than 10! = 10*9*8*7*6*5*4*3*2*1. – rici May 26 '22 at 05:14
  • 1
    And you *definitely* don't want to generate 25! permutations and throw away the duplicates. I'm not going to even work out how many millions of years that would take. – rici May 26 '22 at 05:16
  • Math is hard lol. Thanks, obviously too tired to think straight. – Terry May 26 '22 at 05:17
  • @Terry: counting permutations is really easy. Say you want all length 10 permutations from 25 different things. There are 25 possible first elements. For each of those are 24 possible second elements, and then 23 possible third elements, and so on until we get to 10 elements. Hence, 25*24*23*22*21*20*19*18*17*16. If that's not cristal clear, try doing something like 5 take 3 (60 possibilities) by hand on a (largish) piece of paper.Be systematic – rici May 26 '22 at 05:53

0 Answers0