fork download 
  1. #!perl
  2.  
  3. use strict;
  4. use warnings;
  5. use bigint;
  6.  
  7.  
  8. sub nth_permutation($$$){
  9. 	my ($n, $k, $p) = @_;
  10.  
  11. 	my @choices =  ();
  12. 	for my $i (0..$k-1) {
  13. 		$choices[$i] = $p % ($n - $k + $i + 1);
  14. 		for my $j (0..$i-1) {
  15. 			$choices[$j] ++ if ($choices[$j] >= $choices[$i] )  ; 
  16. 		}
  17. 		$p /= $n - $k + $i + 1;
  18. 	}
  19. 	return reverse @choices;
  20. }
  21.  
  22. sub permno($$@) {
  23. 	my ($n, $k, @choices) = @_;
  24. 	my $p = 0;
  25. 	my $d = 1;
  26. 	$d *= $_ for ($n-$k+1 .. $n-1);  
  27.  
  28. 	for my $i ( 0 .. $k -1) {
  29. 		my $c = $choices[$i];
  30. 		for my $j (0 .. $i-1) {
  31. 			$c -- if $choices[$j] < $choices[$i];
  32. 		}
  33. 		$p += $c * $d;
  34. 		$d /= $n-($i+1);
  35. 	}
  36. 	return $p;
  37.  
  38.  
  39. }
  40.  
  41. sub combno($$@) {
  42.     my ($n, $k, @choices) = @_;
  43.     my $p = 0;
  44.  
  45.     my $index = 0;
  46.  
  47.     my $nk = nchoosek( $n, $k );
  48.  
  49.     for my $i ( 0 .. $k -1) {
  50.             $nk *= ($k - $i);
  51.             $nk /= $n - $index - ($k - $i) + 1;
  52.  
  53.             my $c = $choices[$i];
  54.  
  55.             while ($index < $c ) {
  56.  
  57.                     $nk *= $n-$index - ($k -$i - 1);
  58.                     $nk /= $n-$index;
  59.  
  60.                     $p += $nk;
  61.                     $index ++;
  62.             }
  63.             $nk *= $n-$index - ($k -$i - 1);
  64.             $nk /= $n-$index;
  65.  
  66.             $index ++;
  67.     }
  68.     return $p;
  69. }
  70.  
  71.  
  72. sub nchoosek($$) { 
  73. 	my ($n, $k) = @_;
  74. 	my $p = 1;
  75. 	$p *= $_ for ( $k+1 .. $n) ;
  76. 	$p /= $_ for ( 2 .. $n-$k) ; 
  77. 	return $p;
  78. }
  79.  
  80. sub nth_combination ($$$) {
  81. 	my ($n, $k, $p) = @_;
  82.  
  83.  
  84. 	my @choices = (0);
  85. 	for my $i (0..$k-1) {
  86.  
  87. 		if ($i > 0 ) {$choices[$i]= $choices[$i-1]+1; }
  88.  
  89. 		for my $c ($choices[$i] .. $n - $k + $i + 1) {
  90.  
  91. 			my $n_c = nchoosek($n - 1 - $choices[$i], $k - 1 - $i);
  92. 			last if $n_c > $p;			
  93. 			$p -= $n_c;
  94. 			$choices[$i]++;
  95. 		}
  96. 	}
  97. 	return @choices;
  98. }
  99.  
  100. while (<>) {
  101. 	my ($mode, @vals) = split;
  102.  
  103. 	if ($mode =~ /^pn/) {
  104. 		my ($n, $k, @c) = @vals;
  105. 		my $p = permno($n, $k, @c);
  106. 		print $p . "\n";
  107. 	}
  108. 	elsif ($mode =~ /^p/) {
  109. 		my ($n,$k,$p) = @vals;
  110. 		my @c = nth_permutation($n,$k,$p);
  111. 		print join(',',@c) . "\n";
  112. 	}
  113. 	elsif ($mode =~ /^cn/) {
  114. 		my ($n, $k, @c) = @vals;
  115. 		my $p = combno($n, $k, @c);
  116. 		print $p . "\n";
  117. 	}
  118. 	else {
  119. 		my ($n,$k,$p) = @vals;
  120. 		my @c = nth_combination($n,$k,$p);
  121. 		print join(',',@c) . "\n";
  122. 	}
  123.  
  124. }
  125.  
  126.  
  127.  
Success #stdin #stdout 0.61s 8672KB
comments ()
stdin 
p  42 42  12345678901234 
pn 42 42  25 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 35 32 36 34 39 29 27 33 26 37 40 30 31 41 28 38
cn 100 4 0 1 2 88
cn 120 5 0 1 2 88 111
cn 100 7 15 25 35 45 55 65 85 
c 100 5 12345678
stdout 
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,35,32,36,34,39,29,27,33,26,37,40,30,31,41,28,38
836313165329095177704251551336018791641145678901234
85
6312
11284989655
3,17,24,50,83
https://ideone.com/IWtciv
language:
Perl (perl 5.28.1)
created:
8 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!