Comment trouver la permutation d'une chaîne donnée avec son rang?

Question

Par exemple,

rank permutation 
0  abc 
1  acb 
2  bac 
3  bca 
4  cab 
5  cba 

Donc, si l'on demande me donne permutation avec le rang 4, la réponse est la cabine. Pls donne le code Java pour ce programme

Answer 1

Je l'ai fait à un premier essai !! :-) Vraiment bien fait, gentil problème, tu as fait ma journée! Voici une solution en javascript:

function permutation (rank, n, chars) 
{ 
    var fact, char_idx, this_char; 

    if (n == 0) 
     return ""; 

    char_idx = Math.floor(rank/factorial(n - 1)); 

    this_char = chars.splice(char_idx, 1); 
     // returns the char with index char_idx and removes it from array 

    return this_char + 
     permutation(rank % factorial(n - 1), n - 1, chars); 
} 

suffit d'appeler comme permutation(5, 3, ['a', 'b', 'c']) et c'est tout. Vous devez écrire votre propre fonction factorielle() - comme un devoir :-)

Answer 2

Voici la version aC#: idée de base est d'utiliser factorielle pour déterminer la permutation, plutôt que d'essayer d'obtenir toutes les permutations (vous peut se référer à mon blog @http://codingworkout.blogspot.com/2014/08/kth-permutation.html)

public string GetKthPermutation(string s, int k, int[] factorial) 
     { 
      if (k == 1) 
      { 
       return s; 
      } 
      Assert.IsTrue(k > 1); 
      int numbeOfPermutationsWithRemainingElements = factorial[s.Length-1]; 
      string permutation = null; 
      if (k <= numbeOfPermutationsWithRemainingElements) 
      { 
       //just find the kthPermutation using remaining elements 
       permutation = s[0] + this.GetKthPermutation(s.Substring(1), k, 
        factorial); 
       return permutation; 
      } 
      int quotient = k/numbeOfPermutationsWithRemainingElements; 
      int remainder = k % numbeOfPermutationsWithRemainingElements; 
      Assert.IsTrue(quotient > 0); 
      int indexOfCurrentCharacter = quotient; 
      if(remainder == 0) 
      { 
       indexOfCurrentCharacter -= 1; 
      } 
      permutation = s[indexOfCurrentCharacter].ToString(); 
      Assert.IsTrue(indexOfCurrentCharacter > 0); 
      Assert.IsTrue(indexOfCurrentCharacter < s.Length); 
      string remainingCharactersString = s.Substring(0, indexOfCurrentCharacter); 
      if(indexOfCurrentCharacter < (s.Length-1)) 
      { 
       remainingCharactersString += s.Substring(indexOfCurrentCharacter + 1); 
      } 
      if(remainder == 0) 
      { 
       k = numbeOfPermutationsWithRemainingElements; 
      } 
      else 
      { 
       k = remainder; 
      } 
      permutation += this.GetKthPermutation(remainingCharactersString, k, factorial); 
      return permutation; 
     } 

où

public string GetKthPermutation(string s, int k) 
     { 
      s.ThrowIfNullOrWhiteSpace("a"); 
      k.Throw("k", ik => ik <= 0); 
      int[] factorial = new int[s.Length+1]; 
      factorial[0] = 0; 
      factorial[1] = 1; 
      for(int i =2;i<=s.Length; i++) 
      { 
       factorial[i] = factorial[i - 1] * i; 
      } 
      if(k > factorial[s.Length]) 
      { 
       throw new Exception(string.Format("There will be no '{0}' permuation as the total number of permutations that can be abieved are '{1}'", k, s.Length)); 
      } 
      string kthPermutation = this.GetKthPermutation(s, k, factorial); 
      return kthPermutation; 
     } 

test unitaire

[TestMethod] 
     public void KthPermutationTests() 
     { 
      string s1 = "abc"; 
      string[] perms1 = { "abc", "acb", "bac", "bca", "cab", "cba"}; 
      for(int i =1;i<=6;i++) 
      { 
       string s = this.GetKthPermutation(s1, i); 
       Assert.AreEqual(s, perms1[i - 1]); 
       string ss = this.GetKthPermutation_BruteForce(s1, i); 
       Assert.AreEqual(ss, s); 
      } 
      s1 = "123"; 
      perms1 = new string[] {"123", "132", "213", "231", "312", "321"}; 
      for (int i = 1; i <= 6; i++) 
      { 
       string s = this.GetKthPermutation(s1, i); 
       Assert.AreEqual(s, perms1[i - 1]); 
       string ss = this.GetKthPermutation_BruteForce(s1, i); 
       Assert.AreEqual(ss, s); 
      } 
      s1 = "1234"; 
      perms1 = new string[] { "1234", "1243", "1324", "1342", "1423", "1432", 
            "2134", "2143", "2314", "2341", "2413", "2431", 
            "3124", "3142", "3214", "3241", "3412", "3421", 
            "4123", "4132", "4213", "4231", "4312", "4321"}; 
      for (int i = 1; i <= 24; i++) 
      { 
       string s = this.GetKthPermutation(s1, i); 
       Assert.AreEqual(s, perms1[i - 1]); 
       string ss = this.GetKthPermutation_BruteForce(s1, i); 
       Assert.AreEqual(ss, s); 
      } 
     }