8 examples of 'generate permutations' in Go

282
func (p *RangeInt) PermutationsAll() uint {
283
	return p.Permutations()
284
}

369
func (c *CharacterClass) PermutationsAll() uint {
370
	return c.Permutations()
371
}

91
func (p *Pointer) Permutation(i uint) error {
92
	permutations := p.Permutations()
93
94
	if i >= permutations {
95
		return &token.PermutationError{
96
			Type: token.PermutationErrorIndexOutOfBound,
97
		}
98
	}
99
100
	// do nothing
101
102
	return nil
103
}

25
func makePermutation(cur, n int, nums, vector []int, taken []bool, ans *[][]int) {
26
	if cur == n {
27
		tmp := make([]int, n)
28
		copy(tmp, vector)
29
		*ans = append(*ans, tmp)
30
		return
31
	}
32
33
	used := make(map[int]bool, n-cur)
34
35
	for i := 0; i < n; i++ {
36
37
		if !taken[i] && !used[nums[i]] {
38
			used[nums[i]] = true
39
40
			// 准备使用 nums[i]，所以，taken[i] == true
41
			taken[i] = true
42
			// NOTICE: 是 vector[cur]
43
			vector[cur] = nums[i]
44
45
			makePermutation(cur+1, n, nums, vector, taken, ans)
46
47
			// 下一个循环中
48
			// vector[cur] = nums[i+1]
49
			// 所以，在这个循环中，恢复 nums[i] 自由
50
			taken[i] = false
51
		}
52
	}
53
}

21
func makePermutation(cur, n int, nums, vector []int, taken []bool, ans *[][]int) {
22
	if cur == n {
23
		tmp := make([]int, n)
24
		copy(tmp, vector)
25
		*ans = append(*ans, tmp)
26
		return
27
	}
28
29
	for i := 0; i < n; i++ {
30
		if !taken[i] {
31
			// 准备使用 nums[i]，所以，taken[i] == true
32
			taken[i] = true
33
			// NOTICE: 是 vector[cur]
34
			vector[cur] = nums[i]
35
36
			makePermutation(cur+1, n, nums, vector, taken, ans)
37
38
			// 下一个循环中
39
			// vector[cur] = nums[i+1]
40
			// 所以，在这个循环中，恢复 nums[i] 自由
41
			taken[i] = false
42
		}
43
	}
44
}

121
func (c *Client) permutation(n int) []int {
122
	if c.Permutation != nil {
123
		return c.Permutation(n)
124
	}
125
126
	var randBuf [8]byte
127
	if _, err := io.ReadFull(rand.Reader, randBuf[:]); err != nil {
128
		panic(err)
129
	}
130
131
	seed := binary.LittleEndian.Uint64(randBuf[:])
132
	rand := mathrand.New(mathrand.NewSource(int64(seed)))
133
134
	return rand.Perm(n)
135
}

78
func nextPermutation1(nums []int) {
79
	// find pivot
80
	pivot := len(nums) - 2
81
	for pivot >= 0 && nums[pivot] >= nums[pivot+1] {
82
		pivot--
83
	}
84
	// find the furthest target in 2nd half
85
	if pivot >= 0 {
86
		target := len(nums) - 1
87
		for target >= 0 && nums[target] <= nums[pivot] {
88
			target--
89
		}
90
		// swap the pivot and target
91
		swap(nums, pivot, target)
92
	}
93
	// reverse the 2nd half
94
	reverse(nums, pivot+1)
95
}

53
func generateBlockerPermutations(origin Square, blockerMaskProgress uint64, currPerm uint64, rook bool) {
54
	if blockerMaskProgress == 0 {
55
		// currPerm represents one possible occupancy pattern on the blocker bitboard
56
		if rook {
57
			dbindex := (currPerm * magicNumberRook[origin]) >> magicRookShifts[origin]
58
			magicMovesRook[origin][dbindex] = rookMovesFromBlockers(origin, currPerm)
59
		} else {
60
			dbindex := (currPerm * magicNumberBishop[origin]) >> magicBishopShifts[origin]
61
			magicMovesBishop[origin][dbindex] = bishopMovesFromBlockers(origin, currPerm)
62
		}
63
		return
64
	}
65
	nextBit := bits.TrailingZeros64(blockerMaskProgress)
66
	blockerMaskProgress &= blockerMaskProgress - 1
67
	without := currPerm
68
	with := currPerm | (uint64(1) << uint8(nextBit))
69
	generateBlockerPermutations(origin, blockerMaskProgress, without, rook)
70
	generateBlockerPermutations(origin, blockerMaskProgress, with, rook)
71
}