fork(3) download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <numeric>
  4.  
  5. using namespace std;
  6.  
  7. typedef int Num;
  8.  
  9. int const MAX_N = 11;
  10.  
  11. Num fact [MAX_N + 1];
  12.  
  13. /// precompute factorials
  14. void prepare (int limit)
  15. {
  16. 	fact[0] = 1;
  17. 	for (int i = 1; i <= limit; i++)
  18. 	{
  19. 		fact[i] = fact[i - 1] * i;
  20. 	}
  21. }
  22.  
  23. /// parameters: permutation perm of 0, 1, ..., len-1, and its length len
  24. /// result: lexicographical number of permutation
  25. Num perm_to_num (int * perm, int len)
  26. {
  27. 	int mask = (1 << len) - 1;
  28. 	Num res = 0;
  29. 	for (int pos = 0; pos < len; pos++)
  30. 	{
  31. 		int bit = 1 << perm[pos];
  32. 		int add = __builtin_popcount (mask & (bit - 1));
  33. 		res += add * fact[len - pos - 1];
  34. 		mask ^= bit;
  35. 	}
  36. 	assert (mask == 0);
  37. 	return res;
  38. }
  39.  
  40. int main (void)
  41. {
  42. 	prepare (MAX_N);
  43. 	int const len = MAX_N;
  44.  
  45. 	// testing: all permutations of length len
  46. 	int perm [len];
  47. 	iota (perm, perm + len, 0);
  48. 	Num num_check = 0;
  49. 	do
  50. 	{
  51. 		Num num = perm_to_num (perm, len);
  52. 		assert (num == num_check);
  53. 		num_check += 1;
  54. 	}
  55. 	while (next_permutation (perm, perm + len));
  56.  
  57. 	return 0;
  58. }
  59.  
Success #stdin #stdout 1.67s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0E74XW
permutation to its lexicographical number in O(n)
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!