代码之家 › 专栏 › 技术社区 › stevenpcurtis

swift中的堆算法

swift

stevenpcurtis · 技术社区 · 7 年前

然而,我得到的结果各不相同(第二个是错误的,提供了一个重复排列)。出了什么问题,我该怎么解决?

原始实施:

func permutations(_ n:Int, _ a: inout Array<Character>) {
    if n == 1 {print(String(a)); return}
    for i in 0..<n-1 {
        permutations(n-1,&a)
        a.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    permutations(n-1,&a)
}
var arr = Array("ABC".characters)
permutations(arr.count,&arr)

不带inout参数的实现:

func permutations (_ n: Int, _ a: Array<Character>) {
    var ary = a
    if (n == 1){
        print(String(ary));
        return
    }
    for i in 0..<n-1 {
        permutations(n-1, ary)
        ary.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    permutations(n-1, ary)
}
var arr = Array("ABC".characters)
permutations(arr.count,arr)

输出:

输出:ABC BAC CBA BCA ABC BAC

注意,我们在这个输出中没有CAB,而且还有“BAC”和“ABC”的重复。

我不太明白这两者是如何不等价的,我想创建一个没有inout参数的算法版本。

2 回复 | 直到 7 年前

Ricky Mo 7 年前

Array 是 struct 以迅捷的速度传递价值。如果不使用inout,则必须返回数组才能接收更改。在不更新数组的情况下,每个 permutations(n-1, ary) 在for循环中,基本上在交换之前什么都不做。

func permutations (_ n: Int, _ a: Array<Character>) -> Array<Character> {
    var ary = a
    if (n == 1){
        print(String(ary));
        return ary
    }
    for i in 0..<n-1 {
        ary = permutations(n-1, ary)
        ary.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    return permutations(n-1, ary)
}

Shamas S 7 年前

func permutations (_ n: Int, _ a: Array<Character>) -> Array<Character> {
    var ary = a
    if (n == 1){
        print(String(ary));
        return ary
    }
    var array = Array<Character>()
    for i in 0..<n-1 {
        array = i == 0 ? permutations(n-1, ary) : permutations(n-1, array)
        array.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    return permutations(n-1, array)
}

推荐文章

sudoExclamationExclamation · iOS自动布局-高度不能小于ThanOrEqualTo

1 年前

Tom · SwiftUI.sheet导致背景白色闪烁

1 年前

Danil · 种子/填充核心数据的最佳实践?[关闭]

1 年前

Z S · SwiftUI:使用@FocusState。与视图初始化器绑定

1 年前

Robin · LazyVGrid项目预计不会击中测试区域

1 年前

Mahendra · Popover不是从SwiftUI中的项目列表中打开的[重复]

1 年前

Saurabh Saini · 结构下标

1 年前

Alex Smith · 移动到下一个视图控制器后如何显示警报?

1 年前

jnwjack · Swift:初始化不安全可变指针<CGImage?>不分配

1 年前

Moses Harding · 在SwiftUI的ForEach中以绑定和非绑定方式使用数组的单个成员,而不使用索引

1 年前