Programlama görüşmelerde ortak bir görev (röportaj ama benim deneyim değil, bir dize veya bir tamsayı almak ve mümkün olan her permütasyon listesi.

Bu nasıl yapılır bir örnek ve böyle bir problem çözme mantığı var mı?

Birkaç kod parçacıkları gördüm ama iyi açıklanmış ve böylece sıkı takip/yorum değillerdi.

Birincisi: gibi kokuyorözyinelemeelbette.

Ayrıca prensibini bilmek istedim bu yana, insan dili açıklamak için elimden geleni yaptım. Özyineleme çok kolay çoğu kez düşünüyorum. Sadece iki adım kavramak için:

1. İlk adım
2. Tüm diğer adımları (aynı mantıkla)

insan dili:

Kısacası:

Örnek:

Set sadece bir element^--.perm(a) ->bir

Eğer iki karakter: bu, her öğe: dönüş eleman, permütasyon ile öğeleri geri kalanı gibi: eklendi

perm(ab) ->

perma(b) ->ab

b perm(a) ->ba

Daha: set için her karakter: bir karakter, ^ bir perumation ile birleştirilmiş dönüş . takımın geri kalanı

perm(abc) ->

perma(bc)^--.abc,acb

b perm(ac) -->bac,bca

c perm(ab) -->cab,cba

perm(abc...z) -->

perma(...), b perm (....)

Buldumyalancıhttp://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/:

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation i)
      }
    }
  }
  else {
    add permutation to list
  }
}

C#

TAMAM, ayrıntılı bir şey daha c etiketli olduğundan ( # ), http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : Oldukça uzun, ama bu yazı orijinal bağımlı değildir, onu kopyalamak için zaten karar verdim.

İşlevi "ABC" temin edilmiş, dışarı dökmek gerekir: . Eğer bir karakter dizisi alır ve tam dize her olası permütasyon yazıyor, yani, örneğin,

ABC, ACB, BAC, BCA, CAB, CBA.

Kod:

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);
    }
}