https://blog.demofox.org/2023/08/22/permutation-iteration-and-random-access/ The blog at the bottom of the sea Programming, Graphics, Gamedev, Exotic Computation, Audio Synthesis Menu Skip to content * Table of Contents * License * Contact [grand-teton] Permutation Iteration and Random Access demofox2August 22, 20230 This post has an interesting link to the last one (Inverting Gauss' Formula). The last post was focused on adding all the numbers from 1 to N, this post will feature multiplying all the numbers from 1 to N. We aren't going to be doing it in constant time though, if you want that check out this page: https://devblogs.microsoft.com/oldnewthing/ 20151214-00/?p=92621. Calculating The Number of Permutations Let's say we have 3 letters A,B,C. How many ways are there to arrange them? If you look at is as if we have 3 slots to fill with letters, the first slot has 3 different possible choices. It can pick A, B or C. When the first slot chooses a letter, the second slot only has 2 letters to choose from, but it can make that choices 3 times, which means there are 3*2=6 options. For the last slot, there is only one letter left, which means there is no choice to make, and we are done. First Letter Choices Second Letter Choices Third Letter Choices A _ _ AB_ ABC AC_ ACB B _ _ BA_ BAC BC_ BCA C _ _ CA_ CAB CB_ CBA Let's see the same table for a 4 letter alphabet. First Letter Second Letter Third Letter Fourth Letter Choices Choices Choices Choices ABC_ ABCD AB_ _ ABD_ ABDC A_ _ _ AC_ _ ACB_ ACBD AD_ _ ACD_ ACDB ADB_ ADBC ADC_ ADCB BAC_ BACD BA_ _ BAD_ BADC B_ _ _ BC_ _ BCA_ BCAD BD_ _ BCD_ BCDA BDA_ BDAC BDC_ BDCA CAB_ CABD CA_ _ CAD_ CADB C_ _ _ CB_ _ CBA_ CBAD CD_ _ CBD_ CBDA CDA_ CDAB CDB_ CDBA DAB_ DABC DA_ _ DAC_ DACB D_ _ _ DB_ _ DBA_ DBAC DC_ _ DBC_ DBCA DCA_ DCAB DCB_ DCBA This is only two data points, but it generalizes. If you have N letters, the first slot has N choices, the second slot has N-1 choices for each of those. The third slot has N-2 for each of those. It continues until the last slot has only 1 choice. The formula for the number of permutations is then: N * (N-1) * (N-2) * ... * 1 If you know the sigma symbol for adding numbers together (\Sigma), capital pi is the same, but for multiplying numbers together (\Pi). You can use that to rewrite the formula this way: \Pi^N_{i=1} N An even easier way is to just write it as a factorial, because that's what it is: N! Number of Letters Permutation Count Product Formula 1 1 1 2 2 1*2 3 6 1*2*3 4 24 1*2*3*4 5 120 1*2*3*4*5 6 720 1*2*3*4*5*6 Calculating an Index (Lexicographic Rank) From a Permutation String Let's say you have a 4 letter alphabet (A, B, C, D), and you want to know the index of the permutation string "CBAD". The index you are looking for is called the Lexicographic rank, and it tells you where this string would be if you had all possible strings and sorted them alphabetically. The intuition for calculating this index is realizing that it is also the number of words that would come before it in that sorted list. So, we look at the first letter in "CBAD" and see that it is a C. Anything with an A in the first letter position would come first. That is all the strings of the form "A _ _ _". There are 3 empty slots, with 3 letters to choose from, so this means there are 3! = 3 * 2 * 1 = 6 words that start with the letter A. Our index is at least 6 then. Also, any word with a "B" in the first slot would come earlier, so that's another 6 words that would come before our word. Our index is at least 12 then, because we have found 12 words that would come before our word. Moving on from the first digit, we see that the second slot has a "B". Any word that begins with "CA" would come before our word. That is all words of the form "CA _ _". There are 2 empty slots with 2 letters to fill them in, so that is 2! = 2 * 1 = 2 more words. We have now found 14 words that would come before ours, so our index is at least 14. We have an A in the third slot of our word "CBAD". No letter is less than A so we are ok there. Lastly we come to the fourth letter D. Plenty of letters are less than D, but we've used them all already! D is the only letter that could go here, so we are done. There are 14 words that would come before "CBAD", so the index - or lexicographic rank - of that word is 14. When looking at a letter in a specific slot in a word to see if there are any letters lower, it's important that you don't consider letters that have already been used, to the left of that slot. Each letter should appear exactly once in every word. Also, by that logic, the last slot of a word has no alternative choices. It has to take whatever letter is left over after the other slots have been filled. There is not going to be any word that only differs in the last slot! If anything about this explanation was unclear, the code section at the end should clear things up. Calculating a Permutation String From an Index (Lexicographic Rank) Let's go the other way. Staying with a 4 letter dictionary, that gives you 4! = 4 * 3 * 2 * 1 = 24 permutations. How would we calculate what string is at index 14? We converted a string into this index in the last section so we already know, but let's pretend that we didn't yet know. The process is very similar to converting from decimal to binary or hexadecimal! We are going to start off by making a sorted list of the letters in our alphabet. We'll need this in our algorithm: letterList = [A, B, C, D] To calculate the letter for the first slot, we calculate how many (N-1)! 's fit into the index. With a 4 letter dictionary, looking for index 14, that means we want to know how many times 6 (aka 3!) goes into 14. The answer is 2, with a remainder of 2. The answer controls the next letter, and the remainder is passed onto the next iteration. So, the first letter of our string is letterList[2], which is C. We'll set the index equal to the remainder we calculated above, which was 2. We will also remove C from the letterList. That leaves us with: letterList = [A, B, D] index = 2 string = C_ _ _ Then we move onto the next slot. We calculate the next factorial lower which is 2 (aka 2!) and then calculate how many times it goes into our index. our index is 2, so 2/2 = 1 with a remainder of 0. We set the second letter of our string to letterList[1], which is B. We set the index equal to the remainder, which is 0. We will also remove B from the letterList. That leaves us with: letterList = [A, D] index = 0 string = CB_ _ We then move onto the next slot, and calculate the next factorial lower, which is 1! or 1. We calculate how many times 1 goes into 0. 0 /1 = 0 with a remainder of 0. We set the third letter of our string to letterList[0], or A. We set the index equalt to the raminder, which is 0. We also remove A from the letterList. That leaves us with: letterList = [D] index = 0 string = CBA_ When filling the last slot we only ever have one choice, so set it equal to letterList[0] to complete the string: CBAD. You can verify that CBAD gave us an index of 14 in the last section, so our process successfully did a "round trip". Code Here's code that implements converting from index to string and from string to index. This code allows you to iterate through permutations, get a string for a specific permutation index, and also allows you to go from string back to index. The program output is below the source code. Enjoy! #include #include static const int c_numLetters = 4; // Returns N! int Factorial(int N) { int ret = 1; for (int i = 2; i <= N; ++i) ret *= i; return ret; } // Given a string (an array of values) of size N, assuming the alphabet is [0,N), returns the lexicographic rank. // The lexicographic rank is the position the string would be in if you had all possible strings and sorted them. // Also assumes each letter in the alphabet appears only once. template int LexicographicRankFromString(const int(&string)[SIZE]) { // Keep track of which letters have already been used, so we know how many lower valued letters would // be possible at each position. bool lettersUsed[SIZE]; for (int i = 0; i < (int)SIZE; ++i) lettersUsed[i] = false; // Calculate the rank int rank = 0; int factorial = Factorial(SIZE - 1); for (int pos = 0; pos < SIZE - 1; ++pos) { // count how many letters could be in this position that are a lower value int lowerLetterCount = 0; for (int letterIndex = 0; letterIndex < string[pos]; ++letterIndex) { if (!lettersUsed[letterIndex]) lowerLetterCount++; } // Add those lower valued strings to the rank rank += lowerLetterCount * factorial; // prepare for next loop factorial /= (SIZE - 1 - pos); lettersUsed[string[pos]] = true; } return rank; } // Returns the string for a given lexicographic rank template void StringFromLexicographicRank(int rank, int(&string)[SIZE]) { // Make the full alphabet. // We could pass this in as a parameter but we need a mutable copy anyways int alphabet[SIZE]; for (int i = 0; i < (int)SIZE; ++i) alphabet[i] = i; // Calculate each letter for each position, based on the rank int factorial = Factorial(SIZE - 1); for (int pos = 0; pos < SIZE - 1; ++pos) { // However many of the current factorial fit into the rank, // that is the index of the alphabet character to put there. int numFactorialsFit = rank / factorial; string[pos] = alphabet[numFactorialsFit]; // remove those factorials from the rank rank = rank % factorial; // remove that value from the alphabet for (int i = numFactorialsFit; i < SIZE - 1; ++i) alphabet[i] = alphabet[i + 1]; // prepare for next loop factorial /= (SIZE - 1 - pos); } // one letter left, no choice on what it could be! string[SIZE - 1] = alphabet[0]; } int main(int argc, char** argv) { static const int c_numPermutations = Factorial(c_numLetters); printf("%i letters have %i permutations\n", c_numLetters, c_numPermutations); // For each permutation... int string[c_numLetters]; for (int index = 0; index < c_numPermutations; ++index) { // Get the string for this index StringFromLexicographicRank(index, string); // Get the index from the string just to show that round tripping works int roundTrip = LexicographicRankFromString(string); // print the index, string and round trip index printf(" [%i] ", index); for (int i = 0; i < c_numLetters; ++i) printf("%c", (char)string[i] + 'A'); printf(" (round trip = %i)\n", roundTrip); } return 0; } [image-9] Closing It's possible to have permutations where the number of letters in the alphabet is more than the number of letters in a word. Here's a breadcrumb to working with that situation! https://www.mathplanet.com /education/algebra-2/discrete-mathematics-and-probability/ permutations-and-combinations This is unrelated, but this video talks about generalizing the factorial function to non integers, and even negative numbers: https: //www.youtube.com/watch?v=v_HeaeUUOnc There is an algorithm to iterate through permutation strings directly, without having to use indices. It's called the "Fischer-Krause algorithm" https://mathsanew.com/articles_html/5/ generating_permutationsli3.html. Hacker news discussion of this post: https://news.ycombinator.com/ item?id=37232451 Share this: * Twitter * Facebook * Like this: Like Loading... Related This entry was posted in Uncategorized. Bookmark the permalink. Post navigation - Inverting Gauss' Formula --------------------------------------------------------------------- Leave a Reply Cancel reply Enter your comment here... [ ] Fill in your details below or click an icon to log in: * * * Gravatar Email (required) (Address never made public) [ ] Name (required) [ ] Website [ ] WordPress.com Logo You are commenting using your WordPress.com account. ( Log Out / Change ) Facebook photo You are commenting using your Facebook account. ( Log Out / Change ) Cancel Connecting to %s [ ] Notify me of new comments via email. [ ] Notify me of new posts via email. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] Search [ ] [S] Archives * August 2023 (2) * April 2023 (1) * March 2023 (3) * February 2023 (2) * January 2023 (1) * October 2022 (1) * August 2022 (1) * July 2022 (4) * June 2022 (2) * March 2022 (2) * February 2022 (4) * January 2022 (2) * December 2021 (2) * July 2021 (1) * June 2021 (2) * April 2021 (2) * November 2020 (2) * October 2020 (1) * July 2020 (3) * June 2020 (4) * May 2020 (4) * March 2020 (4) * February 2020 (1) * January 2020 (2) * December 2019 (2) * October 2019 (1) * August 2019 (1) * July 2019 (1) * June 2019 (2) * May 2019 (2) * March 2019 (1) * November 2018 (2) * August 2018 (2) * July 2018 (2) * June 2018 (3) * April 2018 (2) * March 2018 (4) * January 2018 (1) * December 2017 (1) * November 2017 (4) * October 2017 (4) * September 2017 (1) * August 2017 (2) * July 2017 (4) * June 2017 (1) * May 2017 (2) * April 2017 (1) * March 2017 (5) * February 2017 (2) * January 2017 (3) * December 2016 (5) * November 2016 (1) * October 2016 (3) * September 2016 (3) * August 2016 (2) * July 2016 (2) * June 2016 (2) * May 2016 (1) * April 2016 (3) * March 2016 (4) * February 2016 (6) * January 2016 (1) * December 2015 (3) * November 2015 (2) * October 2015 (3) * September 2015 (5) * August 2015 (7) * July 2015 (3) * June 2015 (3) * May 2015 (2) * April 2015 (6) * March 2015 (6) * February 2015 (6) * January 2015 (3) * December 2014 (2) * November 2014 (1) * August 2014 (5) * July 2014 (1) * June 2014 (2) * May 2014 (1) * March 2014 (3) * February 2014 (3) * January 2014 (3) * November 2013 (1) * October 2013 (1) * September 2013 (3) * July 2013 (4) * June 2013 (4) * May 2013 (5) * November 2012 (1) * October 2012 (1) * September 2012 (11) * June 2012 (1) * May 2012 (3) Categories * assembly (1) * Audio Synthesis (19) * C++ (98) * Coding Style (2) * Computer Science (74) * Cryptography (15) * DSP (1) * Encryption + Security (9) * Fractals (2) * Game Development (97) * Gamedev Commentary (4) * Graphics (87) * Math (90) * My Old Master (2) * Network Programming (1) * Neural Networks (6) * Other (1) * Path Tracing (1) * People Skills (6) * Quantum Computing (4) * Ray Tracing (16) * Research (13) * Shadertoy (10) * Skeletal Animation (3) * Uncategorized (57) Category Cloud assembly Audio Synthesis C++ Coding Style Computer Science Cryptography DSP Encryption + Security Fractals Gamedev Commentary Game Development Graphics Math My Old Master Network Programming Neural Networks Other Path Tracing People Skills Quantum Computing Ray Tracing Research Shadertoy Skeletal Animation Uncategorized Recent Posts * Permutation Iteration and Random Access August 22, 2023 * Inverting Gauss' Formula August 21, 2023 * Random Sampling Experiments: Avoid The Sides! April 7, 2023 * Euler's Best Candidate - For Generating Blue Noise Sample Points, and More March 15, 2023 * Euler's Number & Probability March 12, 2023 Create a website or blog at WordPress.com * Follow Following + [croppe] The blog at the bottom of the sea Join 153 other followers [ ] Sign me up + Already have a WordPress.com account? Log in now. * + [croppe] The blog at the bottom of the sea + Customize + Follow Following + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar Loading Comments... Write a Comment... [ ] Email (Required) [ ] Name (Required) [ ] Website [ ] [Post Comment] %d bloggers like this: [b]