当前位置: 动力学知识库 > 问答 > 编程问答 >

Permutation without repetition C#

问题描述:

I am a beginner at C# and I am looking for a code to return all possible permutations of a set, for example {1, 1, 2}, without repetition: {112, 121, 211}. I found the following link but I do not know how to use it.

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

The code I have tried is as follows. When I try to get permutations of "111" for example, it returns all possible permutations with repetition, i.e. six 111s. But I am looking for something providing permutations without repetition. In more details, 111 is just one permutation not six.

class Program

{

private static void Swap(ref char a, ref char b)

{

if (a == b) return;

a ^= b;

b ^= a;

a ^= b;

}

public static void GetPer(char[] list)

{

int x = list.Length - 1;

GetPer(list, 0, x);

}

private static void GetPer(char[] list, int k, int m)

{

if (k == m)

{

Console.Write(list);

}

else

for (int i = k; i <= m; i++)

{

Swap(ref list[k], ref list[i]);

GetPer(list, k + 1, m);

Swap(ref list[k], ref list[i]);

}

}

static void Main()

{

string str = "sagiv";

char[] arr = str.ToCharArray();

GetPer(arr);

}

}

网友答案:

Since you have not posted any code, one can only guess. But, if you break apart the problem statement, then it sounds as if you only have one problem, which is to de-dupe your input. That is a trivial problem to solve. Here is one way to do it:

string dedupe = new string(input.ToCharArray().Distinct().ToArray()); 

the string dedupe now contains only unique characters in the original string input.

网友答案:

I finally found the code I was looking for.

public static void permute(int[] ps, int start, int n) {

//doSomething(ps);
int tmp = 0;
if (start < n) {
  for (int i = n - 2; i >= start; i--) {
    for (int j = i + 1; j < n; j++) {
      if (ps[i] != ps[j]) {
        // swap ps[i] <--> ps[j]
        tmp = ps[i];
        ps[i] = ps[j];
        ps[j] = tmp;

        permute(ps, i + 1, n);
      }
    }

    // Undo all modifications done by
    // recursive calls and swapping
    tmp = ps[i];
    for (int k = i; k < n - 1;)
      ps[k] = ps[++k];
    ps[n - 1] = tmp;
  }
}

}

分享给朋友:
您可能感兴趣的文章:
随机阅读: