func iterateGPUPartitions(devices []*Device, size int, callback func([][]*Device)) {
	if size <= 0 {
		return
	}
	if size > len(devices) {
		return
	}
	if size == 1 {
		for _, device := range devices {
			callback([][]*Device{[]*Device{device}})
		}
		return
	}
	devices = gpuSetCopyAndAddPadding(devices, size)
	padding := gpuSetCountPadding(devices)
	var iterate func(devices []*Device, size int, accum [][]*Device)
	iterate = func(devices []*Device, size int, accum [][]*Device) {
		if size > len(devices) {
			panic("Internal error in best effort allocation policy")
		}
		if size == len(devices) {
			callback(append(accum, devices))
			return
		}
		iterateGPUSets(devices[1:], size-1, func(set []*Device) {
			set = append([]*Device{devices[0]}, set...)
			p := gpuSetCountPadding(set)
			if !(p == 0 || p == padding) {
				return
			}
			remaining := []*Device{}
			for _, gpu := range devices {
				if !gpuSetContains(set, gpu) {
					remaining = append(remaining, gpu)
				}
			}
			iterate(remaining, size, append(accum, set))
		})
	}
	iterate(devices, size, [][]*Device{})
}
Iterate through all possible partitions of the available GPU devices into
sets of size 'size'. This function walks recursively through each possible
partition and applies a callback function to it.
package gpuallocator
import (
	"fmt"
	"github.com/NVIDIA/gpu-monitoring-tools/bindings/go/nvml"
)
type bestEffortPolicy struct{}
func NewBestEffortPolicy() Policy {
	return &bestEffortPolicy{}
}
func (p *bestEffortPolicy) Allocate(available []*Device, required []*Device, size int) []*Device {
	if size <= 0 {
		return []*Device{}
	}
	if len(available) < size {
		return []*Device{}
	}
	if len(required) > size {
		return []*Device{}
	}
	bestPartition := [][]*Device(nil)
	bestScore := 0
	iterateGPUPartitions(available, size, func(candidate [][]*Device) {
		if !gpuPartitionContainsSetWithAll(candidate, required) {
			return
		}
		score := calculateGPUPartitionScore(candidate)
		if score > bestScore || bestPartition == nil {
			bestPartition = candidate
			bestScore = score
		}
	})
	filteredBestPartition := [][]*Device{}
	for _, set := range bestPartition {
		if gpuSetContainsAll(set, required) {
			filteredBestPartition = append(filteredBestPartition, set)
		}
	}
	if len(filteredBestPartition) == 0 {
		return []*Device{}
	}
	bestSet := filteredBestPartition[0]
	bestScore = calculateGPUSetScore(bestSet)
	for i := 1; i < len(filteredBestPartition); i++ {
		score := calculateGPUSetScore(filteredBestPartition[i])
		if score > bestScore {
			bestSet = filteredBestPartition[i]
			bestScore = score
		}
	}
	return bestSet
}
func gpuSetContains(gpuSet []*Device, gpu *Device) bool {
	for i := range gpuSet {
		if gpuSet[i] == gpu {
			return true
		}
	}
	return false
}
func gpuSetContainsAll(gpuSet []*Device, gpuSubset []*Device) bool {
	for _, gpu := range gpuSubset {
		if !gpuSetContains(gpuSet, gpu) {
			return false
		}
	}
	return true
}
func gpuPartitionContainsSetWithAll(gpuPartition [][]*Device, gpuSubset []*Device) bool {
	for _, gpuSet := range gpuPartition {
		if gpuSetContainsAll(gpuSet, gpuSubset) && gpuSetCountPadding(gpuSet) == 0 {
			return true
		}
	}
	return false
}
func gpuSetCopyAndAddPadding(gpuSet []*Device, size int) []*Device {
	if size <= 0 {
		return []*Device{}
	}
	gpus := append([]*Device{}, gpuSet...)
	for len(gpus)%size != 0 {
		gpus = append(gpus, nil)
	}
	return gpus
}
func gpuSetCountPadding(gpuSet []*Device) int {
	count := 0
	for i := range gpuSet {
		if gpuSet[i] == nil {
			count++
		}
	}
	return count
}
func iterateGPUSets(devices []*Device, size int, callback func([]*Device)) {
	if size <= 0 {
		return
	}
	if size > len(devices) {
		return
	}
	level := 0
	indices := make([]int, size)
	set := make([]*Device, size)
	for {
		if indices[level] == len(devices) {
			if level == 0 {
				break
			}
			level--
			indices[level]++
			continue
		}
		set[level] = devices[indices[level]]
		if level < (size - 1) {
			level++
			indices[level] = indices[level-1] + 1
			continue
		}
		callback(set)
		indices[level]++
	}
}