從Swift中獲取3個獨特的項目 - 每個都有唯一值

Question

我有一個鍵/值對的數組，並且想要檢索隨機數量的項目。不過，我要求這些值是不同的，並且不要多次返回相同的項目。

例如：

Apple  1 
Banana 1 
Orange 2 
Kiwi  2 
Pear  3 
Pineapple 4 

我可能要取回3個獨特的項目。即所有3個都有不同的值，同一個項目不會返回兩次。

在Swift中這樣做最有效的方法是什麼？

Answer 1

如果你的元素是可散列的，你可以使用Set。

import Foundation 

extension CollectionType where Generator.Element : Hashable, Index == Int { 
    func sample(n: Int) -> Set<Generator.Element> { 
    var result = Set<Generator.Element>() 
    while result.count < n { 
     let i = Int(arc4random_uniform(UInt32(count))) 
     result.insert(self[i]) 
    } 
    return result 
    } 
} 

如果你的元素不是可哈希，您可以使用索引，以確保其唯一性：

extension CollectionType where Index == Int { 
    func sample(n: Int) -> [Generator.Element] { 
    var result = Set<Int>() 
    let c = UInt32(count) 
    while result.count < n { 
     result.insert(Int(arc4random_uniform(c))) 
    } 
    return result.map { i in self[i] } 
    } 
} 

第二種方法在這裏假設你從採樣集合不包含重複。

Answer 2

您可以使用此數據結構。

Map<String, Integer> newMap = new HashMap<String, Integer>(); 
    List<Integer> valueList = new ArrayList<Integer>(3); 
    for (Map.Entry<String, Integer> entryMap : map.entrySet()) { 
     if (!valueList.contains(entryMap.getValue()) 
       && valueList.size() < 3) { 
      valueList.add(entryMap.getValue()); 
      newMap.put(entryMap.getKey(), entryMap.getValue()); 
     } 

    } 
    System.out.println(newMap); 

Answer 3

編輯：修改答案以處理不存在3個不同值的情況。在這種情況下返回的數量更少。

使用斯威夫特2和Xcode 7測試版6

由於我不清楚如何陣列這裏宣佈2個不同的可能版本。這種想法在每種情況下都是一樣的。

// in this version the array is declared as follows: 
let myArray01 = [["Apple",1], ["Banana", 2], ["Orange", 2], ["Kiwi",2], ["Pear",3],["Pineapple",4]] 

var myArrayCopy01 = myArray01 // a mutable copy of the array from which items can be safely removed 
var counter01:UInt32 = 5 // the number of items in the array 
var myResult01 = [Array<NSObject>]() 
var interimSelection01: [NSObject] 

while myResult01.count < 3 && counter01 > 0 { // the number of randomly selected items we want 
    interimSelection01 = myArrayCopy01.removeAtIndex(Int(arc4random_uniform(counter01--))) // random selection is removed from mutable copy & counter01-- 
    if !(myResult01.map{$0[1]}).contains(interimSelection01[1]) { 
     myResult01.append(interimSelection01) // if we don't already have 1 with that value 
    } 
} 

print(myResult01) 

---

// in this version the pair is an array of tuples: 
let myArray02: [(fruit: String, value: Int)] = [("Apple",1), ("Banana", 2), ("Orange", 2), ("Kiwi",2), ("Pear",3),("Pineapple",4)] 

var myArrayCopy02 = myArray02 // a mutable copy of the array from which items can be safely removed 
var counter02:UInt32 = 5 // the number of items in the array 
var myResult02 = [(fruit: String, value: Int)]() 
var interimSelection02: (fruit: String, value: Int) 

while myResult02.count < 3 && counter02 > 0 { // the number of randomly selected items we want 
    interimSelection02 = myArrayCopy02.removeAtIndex(Int(arc4random_uniform(counter02--))) // random selection is removed from mutable copy & counter02-- 
    if !(myResult02.map({$0.value}).contains(interimSelection02.value)) { 
     myResult02.append(interimSelection02) // if we don't already have 1 with that value 
    } 
} 

print(myResult02) 

Answer 4

編輯：堅持！我發現這個算法有點偏頗！只有在你不真正關心這個時才使用它。

使用費雪耶茨洗牌算法的一部分，我上CollectionType製成的延伸返回從集合n隨機選擇的元素的Array。適用於任何類型的集合（請參閱示例）。複雜性是O(n)。如果n大於集合中元素的數量，則它不會崩潰，但會隨機返回所有元素。經測試，在雨燕2.0測試版6：

import Darwin 

func randomUpTo(n: Int) -> Int { 
    return Int(arc4random_uniform(UInt32(n))) 
} 

extension CollectionType { 
    func chooseRandom(n : Int = Int.max) -> [Generator.Element] { 
     var values = Array(self) 
     for index in values.indices.dropFirst().reverse().prefix(n) { 
      swap(&values[randomUpTo(index)], &values[index]) 
     } 
     return Array(values.suffix(n)) 
    } 
} 

例子：

(0...20).chooseRandom(10) // [16, 20, 2, 7, 11, 13, 18, 9, 17, 4] 
[1, 3, 5, 7, 9, 11].chooseRandom() // [9, 11, 3, 5, 7, 1] 

[ 
    ("Apple" , 1), 
    ("Banana" , 1), 
    ("Orange" , 2), 
    ("Kiwi"  , 2), 
    ("Pear"  , 3), 
    ("Pineapple", 4) 
].chooseRandom(3) // [("Apple", 1), ("Pineapple", 4), ("Kiwi", 2)] 

編輯：複雜性確實O(n)，但其性能可不好，如果集合包含了很多元素的，因爲他們被複制。我現在正在研究一個懶惰的版本，修正了這個問題。