특정 길이의 조합/순열을 생성합니다.

Question

프로젝트는 더 복잡하지만 차단 문제는 다음과 같습니다. 목록에서 특정 길이의 단어 시퀀스 생성 방법은 무엇입니까?

가능한 모든 조합을 생성하는 방법을 찾았지만 (아래 참조) 문제는 특정 길이의 조합 만 필요하다는 것입니다.

Permutations[{a, b, c, d}, {3}]

예 (가상 이동) :

list := []string{"alice", "moon", "walks", "mars", "sings", "guitar", "bravo"} 
    var premutationOf3 
    premutationOf3 = premuate(list, 3) 
    // this should return a list of all premutations such 
    // [][]string{[]string{"alice", "walks", "moon"}, []string{"alice", "signs", "guitar"} ....} 

현재 코드

볼프람 작업 예제는 (내가 단지 조합 (순서는 중요하지 않습니다)가 필요하지만 순열을 사용) 가능한 모든 시퀀스를 사전 완성하기 (길이 제한 없음)

Answer 1

나는 Go에 조합을 생성하기위한 회전 알고리즘을 구현합니다.

package twiddle 

// Twiddle type contains all information twiddle algorithm 
// need between each iteration. 
type Twiddle struct { 
    p []int 
    b []bool 
    end bool 
} 

// New creates new twiddle algorithm instance 
func New(m int, n int) *Twiddle { 
    p := make([]int, n+2) 
    b := make([]bool, n) 

    // initiate p 
    p[0] = n + 1 

    var i int 

    for i = 1; i != n-m+1; i++ { 
     p[i] = 0 
    } 
    for i != n+1 { 
     p[i] = i + m - n 
     i++ 
    } 

    p[n+1] = -2 

    if m == 0 { 
     p[1] = 1 
    } 

    // initiate b 
    for i = 0; i != n-m; i++ { 
     b[i] = false 
    } 
    for i != n { 
     b[i] = true 
     i++ 
    } 

    return &Twiddle{ 
     p: p, 
     b: b, 
    } 
} 

// Next creates next combination and return it. 
// it returns nil on end of combinations 
func (t *Twiddle) Next() []bool { 
    if t.end { 
     return nil 
    } 

    r := make([]bool, len(t.b)) 
    for i := 0; i < len(t.b); i++ { 
     r[i] = t.b[i] 
    } 

    x, y, end := t.twiddle() 
    t.b[x] = true 
    t.b[y] = false 
    t.end = end 

    return r 
} 

func (t *Twiddle) twiddle() (int, int, bool) { 
    var i, j, k int 
    var x, y int 

    j = 1 
    for t.p[j] <= 0 { 
     j++ 
    } 

    if t.p[j-1] == 0 { 
     for i = j - 1; i != 1; i-- { 
      t.p[i] = -1 
     } 
     t.p[j] = 0 
     x = 0 
     t.p[1] = 1 
     y = j - 1 
    } else { 
     if j > 1 { 
      t.p[j-1] = 0 
     } 
     j++ 
     for t.p[j] > 0 { 
      j++ 
     } 
     k = j - 1 
     i = j 
     for t.p[i] == 0 { 
      t.p[i] = -1 
      i++ 
     } 
     if t.p[i] == -1 { 
      t.p[i] = t.p[k] 
      x = i - 1 
      y = k - 1 
      t.p[k] = -1 
     } else { 
      if i == t.p[0] { 
       return x, y, true 
      } 

      t.p[j] = t.p[i] 
      t.p[i] = 0 
      x = j - 1 
      y = i - 1 
     } 
    } 
    return x, y, false 

} 

당신이 다음과 같이 내 지저귐 패키지를 사용할 수 있습니다 : 여기 내 구현

tw := tweedle.New(1, 2) 

for b := tw.Next(); b != nil; b = tw.Next() { 
    fmt.Println(b) 
}