1. 홈
  2. 질의 응답
  3. 주어진 숫자 집합에 대한 순열을 효율적으로 생성하는 코드 C#

주어진 숫자 집합에 대한 순열을 효율적으로 생성하는 코드 C#

2009-10-28 8 views

답변

0

조금 너무 늦게 ... 그냥 참고로. ..

내 테스트에 따르면, 내 구현 Heap's algorithm의 성능은 내가 본 것 중에서 가장 빠른 성능을 제공하는 것으로 보인다.

장점 :

  • 힙의 알고리즘 (순열 당 단일 스왑)
  • 없음 곱셈 안전하지 않은 코드
  • 일반
  • 인라인 된 스왑 (웹에서 본 일부 구현 등)
  • 해당 장소에 (매우 낮은 메모리 사용)
  • 없음 모듈로하지 Heap's algorithm의

내 구현 (단지 첫 번째 비트는 비교) :

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 
using System.Runtime.CompilerServices; 

namespace WpfPermutations 
{ 
    /// <summary> 
    /// EO: 2016-04-14 
    /// Generator of all permutations of an array of anything. 
    /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 
    /// </summary> 
    public static class Permutations 
    { 
     /// <summary> 
     /// Heap's algorithm to find all pmermutations. Non recursive, more efficient. 
     /// </summary> 
     /// <param name="items">Items to permute in each possible ways</param> 
     /// <param name="funcExecuteAndTellIfShouldStop"></param> 
     /// <returns>Return true if cancelled</returns> 
     public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop) 
     { 
      int countOfItem = items.Length; 

      if (countOfItem <= 1) 
      { 
       return funcExecuteAndTellIfShouldStop(items); 
      } 

      var indexes = new int[countOfItem]; 
      for (int i = 0; i < countOfItem; i++) 
      { 
       indexes[i] = 0; 
      } 

      if (funcExecuteAndTellIfShouldStop(items)) 
      { 
       return true; 
      } 

      for (int i = 1; i < countOfItem;) 
      { 
       if (indexes[i] < i) 
       { // On the web there is an implementation with a multiplication which should be less efficient. 
        if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same. 
        { 
         Swap(ref items[i], ref items[indexes[i]]); 
        } 
        else 
        { 
         Swap(ref items[i], ref items[0]); 
        } 

        if (funcExecuteAndTellIfShouldStop(items)) 
        { 
         return true; 
        } 

        indexes[i]++; 
        i = 1; 
       } 
       else 
       { 
        indexes[i++] = 0; 
       } 
      } 

      return false; 
     } 

     /// <summary> 
     /// This function is to show a linq way but is far less efficient 
     /// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer 
     /// </summary> 
     /// <typeparam name="T"></typeparam> 
     /// <param name="list"></param> 
     /// <param name="length"></param> 
     /// <returns></returns> 
     static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length) 
     { 
      if (length == 1) return list.Select(t => new T[] { t }); 

      return GetPermutations(list, length - 1) 
       .SelectMany(t => list.Where(e => !t.Contains(e)), 
        (t1, t2) => t1.Concat(new T[] { t2 })); 
     } 

     /// <summary> 
     /// Swap 2 elements of same type 
     /// </summary> 
     /// <typeparam name="T"></typeparam> 
     /// <param name="a"></param> 
     /// <param name="b"></param> 
     [MethodImpl(MethodImplOptions.AggressiveInlining)] 
     static void Swap<T>(ref T a, ref T b) 
     { 
      T temp = a; 
      a = b; 
      b = temp; 
     } 

     /// <summary> 
     /// Func to show how to call. It does a little test for an array of 4 items. 
     /// </summary> 
     public static void Test() 
     { 
      ForAllPermutation("123".ToCharArray(), (vals) => 
      { 
       Console.WriteLine(String.Join("", vals)); 
       return false; 
      }); 

      int[] values = new int[] { 0, 1, 2, 4 }; 

      Console.WriteLine("Ouellet heap's algorithm implementation"); 
      ForAllPermutation(values, (vals) => 
      { 
       Console.WriteLine(String.Join("", vals)); 
       return false; 
      }); 

      Console.WriteLine("Linq algorithm"); 
      foreach (var v in GetPermutations(values, values.Length)) 
      { 
       Console.WriteLine(String.Join("", v)); 
      } 

      // Performance Heap's against Linq version : huge differences 
      int count = 0; 

      values = new int[10]; 
      for (int n = 0; n < values.Length; n++) 
      { 
       values[n] = n; 
      } 

      Stopwatch stopWatch = new Stopwatch(); 

      ForAllPermutation(values, (vals) => 
      { 
       foreach (var v in vals) 
       { 
        count++; 
       } 
       return false; 
      }); 

      stopWatch.Stop(); 
      Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); 

      count = 0; 
      stopWatch.Reset(); 
      stopWatch.Start(); 

      foreach (var vals in GetPermutations(values, values.Length)) 
      { 
       foreach (var v in vals) 
       { 
        count++; 
       } 
      } 

      stopWatch.Stop(); 
      Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); 
     } 
    } 
}

사용 예 : 숫자 주어진의 [순열의

ForAllPermutation("123".ToCharArray(), (vals) => 
    { 
     Console.WriteLine(String.Join("", vals)); 
     return false; 
    }); 

int[] values = new int[] { 0, 1, 2, 4 }; 
ForAllPermutation(values, (vals) => 
     { 
      Console.WriteLine(String.Join("", vals)); 
      return false; 
     });

출처

2016-04-18 14:23:46

0 
public static IEnumerable<T[]> Permute<T>(T[] array) 
    { 
     for(int i=0; i<array.Length; i++) 
     { 
      if (array.Length <= 1) 
      { 
       yield return array; 
      } 
      else 
      { 
       T[] except = new T[array.Length - 1]; 
       Array.Copy(array, except, i); 
       Array.Copy(array, i + 1, except, i, array.Length - i - 1); 
       foreach (T[] sub in Permute(except)) 
       { 
        T[] answer = new T[sub.Length + 1]; 
        Array.Copy(sub, 0, answer, 1, sub.Length); 
        answer[0] = array[i]; 
        yield return answer; 
       } 
      } 
     } 
    }

출처

2018-01-24 11:14:11 user2882061

관련 문제

 관련 문제