UTXO选择策略

Question

我需要在选择 UTXO 时应用特定策略。该策略应尽可能减少 utxo 的使用。应设置此策略的边界，理想情况下，应支持较少数量的 utxo 直到 10 倍比率。

为了简化问题让我们假设，有一个整数列表 := []int{} 的切片，我需要找到元素 'target' 其中： list[index] = target，如果这样的元素不存在，那么我需要从 slice 中找到第一个大于 target 但需要 <= target*10

的元素

如果我找不到这样的元素，那么我需要找到两个元素 x, y，其中： x + y = target，如果这样的元素不存在，我需要从 slice 中找到前两个大于 target 但需要 <= target*10

的元素

如果我找不到这样的元素，那么我需要找到三个元素 x、y、z，其中： x + y + z = target，如果这样的元素不存在，我需要从 slice 中找到前三个大于 target 但需要 <= target*10

的元素

如果我找不到这样的三个元素，我需要找到四个，五个...直到 len(list)。

示例 1：

target = 6
list := []int {1,2, 6, 10}
result = list[2] = 6

示例 2：

target = 6
list := []int {1,2, 3, 10}
result = list[3] = 10

示例 3：

target = 6
list := []int {1,2, 3, 10}
result = list[3] = 10

示例 4：

target = 6
list := []int {1,3, 3, 61}
result = list[1]  + list[2]= 6

请参阅下面的测试用例，我需要通过递归或某种方式改进以获得通用解决方案：

func Test_SelectUtxo(t *testing.T){
    x := 6

    list := []int{1, 2, 3, 64, 65, 62, 62, 62, 61, 59}
    
    fmt.Println("ONE = x")
    for i := 0; i < len(list) - 1; i ++ {
        if list[i] == x {
            fmt.Println(i)
            break
        }
    }

    fmt.Println("ONE <= x*10")
    for i := 0; i < len(list); i ++ {
        if list[i] > x {
            if list[i] <= x*10 && list[i] > x {
                fmt.Println(list[i])
                break
            }
        }
    }


    fmt.Println("TWO = x")
    out:
    for i := 0; i < len(list) - 1; i ++ {
        for j:=i + 1; j < len(list); j ++ {
            if list[i] + list[j] == x {
                fmt.Println(i)
                fmt.Println(j)
                break out
            }
        }
    }

    fmt.Println()

    fmt.Println("TWO <= x*10")
    out1:
    for i := 0; i < len(list) - 1; i ++ {
        for j:=i + 1; j < len(list); j ++ {
            if list[i] + list[j] <= x*10 && list[i] + list[j] > x {
                fmt.Println(i)
                fmt.Println(j)
                break out1
            }
        }
    }

    fmt.Println()

    fmt.Println("THREE = x")
    out2:
    for i := 0; i < len(list) - 2; i ++ {
        for j:=i + 1; j < len(list) - 1; j ++ {
            for k:= j + 1; k < len(list); k ++ {
                if list[i] + list[j] + list[k] == x {
                    fmt.Println(i)
                    fmt.Println(j)
                    fmt.Println(k)
                    break out2
                }
            }
        }
    }

}

Answer 1

一解：

设置size = 1
使用Recursion（下面代码段中的函数名称=getCombination）获取[=13=的所有组合] 输入数组中的元素。
检查每个组合是否符合0 -> i的要求，如果是，return它（完成)
如果 none 个组合匹配，则 size++，然后转到 步骤 2。

片段：

import (
  "fmt"
)
var combination = []int{}
func GetCombination(src []int,size int, offset int) [][]int { // get all combinations for **size** elements in the elements of src array
  result := [][]int{}
  if size == 0 {
    temp := make([]int, len(combination))
    copy(temp, combination)
    return append(result, temp)
  }
  for i:=offset; i<=len(src) - size; i++ {
    combination = append(combination, src[i])
    temp := GetCombination(src, size-1, i+1)
    result = append(result, temp...)
    combination = combination[:len(combination)-1]
  }
  return result[:]
}
func sum(items []int) int {
  total := 0
  for _, v := range items {
    total += v
  }
  return total
}
func GetBestPair(items []int, target int) []int {
    for i := 1; i < len(items)+1; i++ {
        result := GetCombination(items, i, 0) // get all possible combinations for 1 -> len(items) elements of Array=items
        // fmt.Println("Combinations for ", i, " elements:", result)
        for j := 0; j < len(result); j++ {
            total := sum(result[j])
            if total < target {
                continue
            }
            if total == target {
                return result[j]
            }
            if total < target*10 {
                return result[j]
            }
        }
    }
    return []int{}
}

func main () {
  fmt.Println("Result", GetBestPair([]int{1, 3, 3, 61}, 6))
}

上述测试用例的输出

Combinations for  1  elements: [[1] [3] [3] [61]]
Combinations for  2  elements: [[1 3] [1 3] [1 61] [3 3] [3 61] [3 61]]
Result: [3 3]

UTXO选择策略

UTXO selection strategy

algorithm

go

bitcoin