shuffle card deck issues in language agnostic
不久前，我在接受采访时要求解决两个非常有趣的问题。我很好奇您将如何解决这些问题。
问题1：
除电流外的所有产品
编写一个函数，该函数将长度为len的两个整数数组，输入和索引作为输入，并生成第三个数组，结果如下：
result [i] =输入中除input [index [i]]以外的所有内容的乘积
例如，如果使用len = 4，input = {2,3,4,5}和index = {1,3,2,0}调用函数，则结果将设置为{40,24,30 ，60}。
重要说明：您的算法必须在线性时间内运行。
问题2 ：(该主题在Jeff的一篇文章中)
均匀洗牌
设计(使用C ++或C＃)类Deck代表有序纸牌，其中纸牌包含52张纸牌，分为13个等级(A，2、3、4、5、6、7、8、9，四个花色中的10，J，Q，K)：黑桃(？)，心形(？)，钻石(？)和球杆(？)。
基于此类，设计并实现一种有效的算法来洗牌。纸牌必须均匀地混洗，也就是说，原始纸牌中的每张纸牌必须具有相同的概率才能出现在纸牌中的任何可能位置。
该算法应在Deck类的shuffle()方法中实现：
无效shuffle()
您的算法的复杂度是多少(取决于卡片组中n张卡片的数量)？
解释如何测试卡是否被您的方法均匀洗净(黑盒测试)。
附言我有两个小时编写解决方案的代码
第一个问题：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| int countZeroes (int[] vec) {
int ret = 0;
foreach(int i in vec) if (i == 0) ret++;
return ret;
}
int[] mysticCalc(int[] values, int[] indexes) {
int zeroes = countZeroes(values);
int[] retval = new int[values.length];
int product = 1;
if (zeroes >= 2) { // 2 or more zeroes, all results will be 0
for (int i = 0; i > values.length; i++) {
retval[i] = 0;
}
return retval;
}
foreach (int i in values) {
if (i != 0) product *= i; // we have at most 1 zero, dont include in product;
}
int indexcounter = 0;
foreach(int idx in indexes) {
if (zeroes == 1 && values[idx] != 0) { // One zero on other index. Our value will be 0
retval[indexcounter] = 0;
}
else if (zeroes == 1) { // One zero on this index. result is product
retval[indexcounter] = product;
}
else { // No zeros. Return product/value at index
retval[indexcounter] = product / values[idx];
}
indexcouter++;
}
return retval;
} |
最坏的情况是，该程序将一次执行3个向量。
除Python外的所有产品的乘积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| from numpy import array
def product(input, index):
a = array(input)[index]
if a[a == 0].size != 1:
a = a.prod() / a # product except current
else:
# exaclty one non-zero-valued element in `a`
nzi = a.nonzero() # indices of non-zero-valued elements
a[a == 0] = a[nzi].prod()
a[nzi] = 0
return a |
例：
1
2
| for input in ([2,3,4,5], [2,0,4,5], [0,3,0,5]):
print product(input, [1,3,2,0]) |
输出：
1
2
3
| [40 24 30 60]
[40 0 0 0]
[0 0 0 0] |
在Haskell中：
1
2
3
4
5
6
| import Array
problem1 input index = [(left!i) * (right!(i+1)) | i <- index]
where left = scanWith scanl
right = scanWith scanr
scanWith scan = listArray (0, length input) (scan (*) 1 input) |
这是使用测试方法在C＃中第二个答案的答案。 Shuffle在我看来是O(n)。
编辑：查看了Fisher-Yates随机播放后，我发现我不知道它就重新发明了该算法:-)但是很明显。我实现了Durstenfeld方法，将我们从O(n ^ 2)-> O(n)引入，非常聪明！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| public enum CardValue { A, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, J, Q, K }
public enum Suit { Spades, Hearts, Diamonds, Clubs }
public class Card {
public Card(CardValue value, Suit suit) {
Value = value;
Suit = suit;
}
public CardValue Value { get; private set; }
public Suit Suit { get; private set; }
}
public class Deck : IEnumerable<Card> {
public Deck() {
initialiseDeck();
Shuffle();
}
private Card[] cards = new Card[52];
private void initialiseDeck() {
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 13; ++j) {
cards[i * 13 + j] = new Card((CardValue)j, (Suit)i);
}
}
}
public void Shuffle() {
Random random = new Random();
for (int i = 0; i < 52; ++i) {
int j = random.Next(51 - i);
// Swap the cards.
Card temp = cards[51 - i];
cards[51 - i] = cards[j];
cards[j] = temp;
}
}
public IEnumerator<Card> GetEnumerator() {
foreach (Card c in cards) yield return c;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
foreach (Card c in cards) yield return c;
}
}
class Program {
static void Main(string[] args) {
foreach (Card c in new Deck()) {
Console.WriteLine("{0} of {1}", c.Value, c.Suit);
}
Console.ReadKey(true);
}
} |
C＃3中第一个问题的线性时间解决方案是：-
1
2
3
4
5
6
7
8
9
| IEnumerable<int> ProductExcept(List<int> l, List<int> indexes) {
if (l.Count(i => i == 0) == 1) {
int singleZeroProd = l.Aggregate(1, (x, y) => y != 0 ? x * y : x);
return from i in indexes select l[i] == 0 ? singleZeroProd : 0;
} else {
int prod = l.Aggregate(1, (x, y) => x * y);
return from i in indexes select prod == 0 ? 0 : prod / l[i];
}
} |
编辑：考虑到一个零！我上一次的解决方案是在我上班的时候花了2分钟，所以我不会觉得很糟糕:-)
C中除电流以外的所有乘积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void product_except_current(int input[], int index[], int out[],
int len) {
int prod = 1, nzeros = 0, izero = -1;
for (int i = 0; i < len; ++i)
if ((out[i] = input[index[i]]) != 0)
// compute product of non-zero elements
prod *= out[i]; // ignore possible overflow problem
else {
if (++nzeros == 2)
// if number of zeros greater than 1 then out[i] = 0 for all i
break;
izero = i; // save index of zero-valued element
}
//
for (int i = 0; i < len; ++i)
out[i] = nzeros ? 0 : prod / out[i];
if (nzeros == 1)
out[izero] = prod; // the only non-zero-valued element
} |
对于第一个，首先计算输入的全部内容的乘积，然后对于索引的每个元素，将计算出的乘积除以input [index [i]]，以填充结果数组。
当然，我必须假设输入没有零。
YXJuLnphcnQ，我也是这样做的。这是最明显的。
但是事实是，如果您编写算法，则每次调用sort()时，都只会将集合中的所有卡向右移一个位置，即使输出不是随机的，也可以通过测试。
Trilsson在问题的测试部分做了一个单独的主题
如何测试随机性(以点为例-改组)
很好的想法Trilsson ：)
在C ++中均匀地随机播放卡座
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include
class Deck {
// each card is 8-bit: 4-bit for suit, 4-bit for value
// suits and values are extracted using bit-magic
char cards[52];
public:
// ...
void shuffle() {
std::random_shuffle(cards, cards + 52);
}
// ...
}; |
复杂度：N中为线性。恰好执行51次交换。参见http://www.sgi.com/tech/stl/random_shuffle.html
测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| // ...
int main() {
typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
Map freqs;
Deck d;
const size_t ntests = 100000;
// compute frequencies of events: card at position
for (size_t i = 0; i < ntests; ++i) {
d.shuffle();
size_t pos = 0;
for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos)
++freqs[std::make_pair(pos, *j)];
}
// if Deck.shuffle() is correct then all frequencies must be similar
for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
std::cout <<"pos=" << j->first.first <<" card=" << j->first.second
<<" freq=" << j->second << std::endl;
} |
像往常一样，一个测试是不够的。
Tnilsson，我还使用了Fisher-Yates洗牌:)。我对测试部分非常感兴趣：)
Tnilsson，我同意YXJuLnphcnQ解决方案可以说是更快的，但思想是相同的。我忘了补充，在第一个问题中该语言是可选的，在第二个问题中该语言是可选的。
没错，该计算为零，并且乘积int相同的循环更好。也许就是这样。
第二个问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static void shuffle (int[] array)
{
Random rng = new Random(); // i.e., java.util.Random.
int n = array.length; // The number of items left to shuffle (loop invariant).
while (n > 1)
{
int k = rng.nextInt(n); // 0 <= k < n.
n--; // n is now the last pertinent index;
int temp = array[n]; // swap array[n] with array[k] (does nothing if k == n).
array[n] = array[k];
array[k] = temp;
}
} |
这是Wikipedia文章中有关Fisher-Yates随机播放的内容的复制/粘贴。 O(n)复杂度
Tnilsson，很好的解决方案(因为我用完全相同的方法：P)。
我看不到在线性时间内完成此操作的其他方法。有人吗？因为招聘经理告诉我，这种解决方案不够强大。
我们是否错过了一些超级复杂的事物，所有事情都在一个返回线中解决吗？
Vaibhav，很遗憾，我们不得不假设输入表中可能有一个0。
|
