Swift - 生成重复组合 [英] Swift - Generate combinations with repetition

问题描述

我正在尝试使用 Apple 的 Swift 编程语言生成一个包含所有重复组合的嵌套数组.

I'm trying to generate a nested array containing all combinations with repetition in Apple's Swift programming language.

可以在本页底部附近找到有关重复组合的详细说明:http://www.mathsisfun.com/combinatorics/combinations-permutations.html

An detailed explanation of combinations with repetition can be found near the bottom of this page: http://www.mathsisfun.com/combinatorics/combinations-permutations.html

简而言之；顺序无关紧要，我们可以重复

Briefly; order does not matter, and we can repeat

n = 我们选择的事物的集合

n = the set of things we are choosing form

r = 我们选择的东西的数量

r = the number of things we are choosing

我想创建一个函数，该函数将生成一个嵌套数组，其中包含对 n 和 r 的任何(小)值进行重复的所有组合.

I want to create a function that will generate a nested array containing all combinations with repetition for any (small) values of n and r.

如果有 n=3 的东西可供选择，我们选择其中的 r=2.

If there are n=3 things to choose from, and we choose r=2 of them.

n = [0, 1, 2]
r = 2

函数 combos(n: [0, 1, 2], r: 2) 的结果是:

result = [
  [0, 0],
  [0, 1],  
  [0, 2],
  [1, 1],
  [1, 2],
  [2, 2]
]

// we don't need [1, 0], [2, 0] etc. because "order does not matter"

这里有许多编程语言的例子:http://rosettacode.org/wiki/Combinations_with_repetitions

There are examples for doing this in many programming languages here: http://rosettacode.org/wiki/Combinations_with_repetitions

这是 PHP 示例.它是最简单的之一，并返回一个数组，这正是我想要的:

Here's the PHP example. It is one of the simplest and returns an array, which is what I want:

function combos($arr, $k) {
    if ($k == 0) {
        return array(array());
    }

    if (count($arr) == 0) {
        return array();
    }

    $head = $arr[0];

    $combos = array();
    $subcombos = combos($arr, $k-1);
    foreach ($subcombos as $subcombo) {
        array_unshift($subcombo, $head);
        $combos[] = $subcombo;
    }
    array_shift($arr);
    $combos = array_merge($combos, combos($arr, $k));
    return $combos;
}

到目前为止，我已经将函数移植到 Swift:

Here's where I've got so far with porting the function to Swift:

func combos(var array: [Int], k: Int) -> AnyObject { // -> Array<Array<Int>> {
    if k == 0 {
        return [[]]
    }
    
    if array.isEmpty {
        return []
    }
    
    let head = array[0]
    
    var combos = [[]]
    var subcombos: [Array<Int>] = combos(array, k-1)    // error: '(@Ivalue [Int], $T5) -> $T6' is not identical to '[NSArray]'
    for subcombo in subcombos {
        var sub = subcombo
        sub.insert(head, atIndex: 0)
        combos.append(sub)
    }
    array.removeAtIndex(0)
    combos += combos(array, k)    // error: '(@Ivalue [Int], Int) -> $T5' is not identical to '[NSArray]'
    
    return combos
}

大多数情况下，我似乎对各种变量的类型声明以及这些变量是可变还是不可变有问题.

Mostly I seem to be having problems with the type declarations of the various variables and whether these are mutable or immutable.

我已经尝试在类型声明中更加明确和不那么明确，但我设法实现的只是略有不同的错误消息.

I've tried being more explicit and less explicit with the type declarations but all I'm managed to achieve are slightly different error messages.

如果有人能解释我哪里出错以及为什么出错，我将不胜感激?

I would be most grateful if someone would explain where I'm going wrong and why?

推荐答案

你可以通过将循环写成

for subcombo in subcombos {
    ret.append([head] + subcombo)
}

这可以使用 map() 函数进一步简化:

This can be further simplified using the map() function:

func combos<T>(var array: Array<T>, k: Int) -> Array<Array<T>> {
    if k == 0 {
        return [[]]
    }

    if array.isEmpty {
        return []
    }

    let head = [array[0]]
    let subcombos = combos(array, k: k - 1)
    var ret = subcombos.map {head + $0}
    array.removeAtIndex(0)
    ret += combos(array, k: k)

    return ret
}

<小时>

Swift 4 更新:

func combos<T>(elements: ArraySlice<T>, k: Int) -> [[T]] {
    if k == 0 {
        return [[]]
    }

    guard let first = elements.first else {
        return []
    }

    let head = [first]
    let subcombos = combos(elements: elements, k: k - 1)
    var ret = subcombos.map { head + $0 }
    ret += combos(elements: elements.dropFirst(), k: k)

    return ret
}

func combos<T>(elements: Array<T>, k: Int) -> [[T]] {
    return combos(elements: ArraySlice(elements), k: k)
}

现在数组 slices 被传递给递归调用以避免许多临时数组的创建.

Now array slices are passed to the recursive calls to avoid the creation of many temporary arrays.

示例:

print(combos(elements: [1, 2, 3], k: 2))
// [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]

这篇关于Swift - 生成重复组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！