복권 순위 조합 찾기

Question

복권 조합의 순위/색인을 찾아 프로세스를 역전시킬 수 있어야합니다 (순위가 주어진 복권 조합 찾기).

1에서 45까지 5 개의 볼과 1에서 20까지의 파워 볼을 사용한 복권 게임을 고려해보십시오. 중복은 허용되지 않으며 순서는 중요하지 않습니다. 조합의 수는 다음과 같습니다

(45 * 44 * 43 * 42 * 41/5!) * 20 = 24,435,180 

첫 번째 조합 (인덱스 0)입니다 :

1, 2, 3, 4, 5, 1 

마지막 조합 (지수 24,435,179)입니다 :

41, 42, 43, 44, 45, 20 

나는 변환 할 수있는 방법 모든 조합을 철저히 열거하지 않고도 색인에 조합 할 수 있습니까?

나는 this 주어진 인덱스의 조합을 얻는 방법을 보여주는 MSDN 문서를 발견했습니다. 그러나 조합에서 색인을 얻는 방법을 모르겠습니다. 나는 시도했다 :

여기서 ci는 정렬 된 조합 세트의 위치 i에있는 번호이고 k는 세트의 크기이다. 조합의 색인은 요소의 범위에 따라 다르므로 작동하지 않습니다. 또한 세트의 크기가 다른 요소 (예 : 주 풀의 범위는 1-45, 파워 볼의 범위는 1-20)로 작동하는지 잘 모르겠습니다.

Answer 1

알아낼 수있었습니다. MSDN example을 기반으로하는 새로운 Combination 클래스를 만들었습니다.이 조합은 인덱스로 조합을 변환하거나 그 반대로도 변환 할 수 있습니다. 각 숫자 풀마다 별도의 색인이 검색됩니다. 그런 다음 모든 색인을 결합하여 크기가 다른 요소와의 조합을 나타냅니다.

풀 클래스 (요소 범위, 크기 등)를 나타내는 풀 클래스도 생성되었습니다. 풀 클래스 :

public class Pool { 
    public int From { get; set; } 
    public int To { get; set; } 
    public int Size { get; set; } 
    public int Numbers { get { return (To - From + 1); } } 
    public Pool(int From, int To, int Size) { 
     this.From = From; 
     this.To = To; 
     this.Size = Size ; 
    } 
} 

조합 클래스 :

class Combination { 

    public Pool[] Pools { get; set; } 
    public long[][] Data { get; set; } //First index represents pool index, second represents the numbers 

    public Combination(Pool[] Pools, long[][] Data) { 
     this.Pools = Pools; 
     this.Data = Data; 
     if (Data.GetLength(0) != Pools.Length) { 
      throw (new ArgumentException("Invalid data length")); 
     } 

     for (int i = 0; i < Data.GetLength(0); i++) { 
      if (Data[i].Length != Pools[i].Size) { 
       throw (new ArgumentException("Invalid data length")); 
      } 
     } 
    } 

    public static Combination FromIndex(long Index, Pool[] Pools) { 
     long[][] elements = new long[Pools.Length][]; 

     long[] c = new long[Pools.Length - 1]; 
     long cumulative = 1; 
     for (int i = 0; i < Pools.Length - 1; i++) { 
      c[i] = Combination.Choose(Pools[i].Numbers, Pools[i].Size); 
      checked { 
       cumulative *= c[i]; 
      } 
     } 

     for (int i = Pools.Length - 1; i >= 1; i--) { 
      long ind = Index/cumulative; 
      Index -= ind * cumulative; 

      cumulative /= c[i - 1]; 
      elements[i] = Combination.FromIndex(ind, Pools[i]); 
     } 
     elements[0] = Combination.FromIndex(Index, Pools[0]); 


     return (new Combination(Pools, elements)); 
    } 

    public static long[] FromIndex(long Index, Pool Pool) { 
     long[] ans = new long[Pool.Size]; 
     long a = (long)Pool.Numbers; 
     long b = (long)Pool.Size; 
     long x = GetDual((long)Pool.Numbers, (long)Pool.Size, Index); 

     for (int k = 0; k < Pool.Size; k++) { 
      ans[k] = LargestV(a, b, x); 
      x -= Choose(ans[k], b); 
      a = ans[k]; 
      b--; 
     } 

     for (int k = 0; k < Pool.Size; k++) { 
      ans[k] = ((long)Pool.Numbers - 1) - ans[k]; 
     } 


     //Transform to relative 
     for (int i = 0; i < ans.Length; i++) { 
      ans[i] += Pool.From; 
     } 

     return (ans); 
    } 

    private static long GetDual(long To, long Size, long m) { 
     return (Choose(To, Size) - 1) - m; 
    } 

    public static long Choose(long To, long Size) { 
     if (To < 0 || Size < 0) 
      throw new Exception("Invalid negative parameter in Choose()"); 
     if (To < Size) 
      return 0; // special case 
     if (To == Size) 
      return 1; 

     long delta, iMax; 

     if (Size < To - Size) { 
      delta = To - Size; 
      iMax = Size; 
     } else { 
      delta = Size; 
      iMax = To - Size; 
     } 

     long ans = delta + 1; 

     for (long i = 2; i <= iMax; ++i) { 
      checked { 
       ans = (ans * (delta + i))/i; 
      } 
     } 

     return ans; 
    } 

    private static long LargestV(long a, long b, long x) { 
     long v = a - 1; 

     while (Choose(v, b) > x) 
      --v; 

     return v; 
    } 

    public long ToIndex() { 
     long Index = 0; 
     long cumulative = 1; 

     for (int i = 0; i < Pools.Length; i++) { 
      checked { 
       Index += ToIndex(i) * cumulative; 
       cumulative *= Combination.Choose(Pools[i].Numbers, Pools[i].Size); 
      } 
     } 

     return (Index); 

    } 

    public long ToIndex(int PoolIndex) { 
     long ind = 0; 
     for (int i = 0; i < Pools[PoolIndex].Size; i++) { 
      long d = (Pools[PoolIndex].Numbers - 1) - (Data[PoolIndex][i] - Pools[PoolIndex].From); 
      ind += Choose(d, Pools[PoolIndex].Size - i); 
     } 

     ind = GetDual(Pools[PoolIndex].Numbers, Pools[PoolIndex].Size, ind); 
     return (ind); 
    } 

    public override string ToString() { 
     string s = "{ "; 

     for (int i = 0; i < Data.Length; ++i) { 
      for (int k = 0; k < Data[i].Length; k++) { 
       s += Data[i][k] + " "; 
      } 
      if (i != Data.Length - 1) { 
       s += "| "; 
      } 
     } 
     s += "}"; 
     return s; 
    } 
} 

행동이를 보려면 :

 //Create pools 
     Pool[] pools = new Pool[2]; 
     pools[0] = new Pool(1, 45, 5); 
     pools[1] = new Pool(1, 20, 1); 

     //Create a combination 
     long[][] data = new long[][] { new long[] { 41, 42, 43, 44, 45 }, new long[] { 20 } }; 
     Combination combination = new Combination(pools, data); 

     //Get index from combination: 
     long index = combination.ToIndex(); 
     Console.WriteLine("Index: " + index); 

     //Get combination from index: 
     Combination combFromIndex = Combination.FromIndex(index, pools); 
     Console.WriteLine("Combination: " + combFromIndex); 

출력 :

Index: 24435179 
Combination: { 41 42 43 44 45 | 20 }