Class: PermutationTest

Inherits:
Test::Unit::TestCase
  • Object
show all
Includes:
MoreMath
Defined in:
tests/permutation_test.rb

Constant Summary

Constants included from MoreMath

MoreMath::Infinity, MoreMath::STD_NORMAL_DISTRIBUTION, MoreMath::VERSION, MoreMath::VERSION_ARRAY, MoreMath::VERSION_BUILD, MoreMath::VERSION_MAJOR, MoreMath::VERSION_MINOR

Instance Method Summary collapse

Instance Method Details

#setup ⇒ Object 



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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'tests/permutation_test.rb', line 9

def setup
  @perms = (0..4).map { |i| Permutation.new(i) }
  @perms_collections = [ "", "a", "ab", "abc", "abcd" ].map do |c|
    Permutation.for(c)
  end
  @perms_each = [
    [[]],
    [[0]],
    [[0, 1], [1, 0]],
    [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]],
    [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1],
      [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2],
      [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0],
      [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0],
      [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1],
      [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
  ]
  @next_pred = [
    [ [], [] ],
    [ [ 0 ], [ 0 ] ],
    [ [ 0, 1 ], [ 1, 0 ] ],
    [ [ 1, 0 ], [ 0, 1 ] ],
    [ [ 0, 1, 2 ], [ 0, 2, 1 ] ],
    [ [ 0, 2, 1 ], [ 1, 0, 2 ] ],
    [ [ 1, 0, 2 ], [ 1, 2, 0 ] ],
    [ [ 1, 2, 0 ], [ 2, 0, 1 ] ],
    [ [ 2, 0, 1 ], [ 2, 1, 0 ] ],
    [ [ 2, 1, 0 ], [ 0, 1, 2 ] ],
  ]
  @projected = [
    [ "" ],
    [ "a" ],
    [ "ab", "ba", ],
    [ "abc", "acb", "bac", "bca", "cab", "cba" ],
    [ "abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd",
      "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb",
      "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac",
      "dbca", "dcab", "dcba"]
  ]
  @products = [
    {[0, 0]=>[]},
    {[0, 0]=>[0]},
    {[0, 0]=>[0, 1], [1, 1]=>[0, 1], [1, 0]=>[1, 0], [0, 1]=>[1, 0]},
    {[2, 4]=>[2, 1, 0], [1, 2]=>[2, 0, 1], [0, 0]=>[0, 1, 2],
      [5, 4]=>[0, 2, 1], [3, 3]=>[2, 0, 1], [2, 1]=>[1, 2, 0],
      [0, 5]=>[2, 1, 0], [3, 5]=>[0, 2, 1], [1, 1]=>[0, 1, 2],
      [0, 3]=>[1, 2, 0], [5, 3]=>[1, 0, 2], [4, 1]=>[2, 1, 0],
      [3, 2]=>[2, 1, 0], [2, 0]=>[1, 0, 2], [0, 4]=>[2, 0, 1],
      [3, 4]=>[0, 1, 2], [1, 0]=>[0, 2, 1], [0, 2]=>[1, 0, 2],
      [5, 2]=>[1, 2, 0], [4, 0]=>[2, 0, 1], [3, 1]=>[1, 0, 2],
      [2, 3]=>[0, 2, 1], [1, 5]=>[1, 2, 0], [4, 5]=>[1, 0, 2],
      [5, 1]=>[2, 0, 1], [4, 3]=>[0, 1, 2], [3, 0]=>[1, 2, 0],
      [2, 2]=>[0, 1, 2], [1, 4]=>[1, 0, 2], [4, 4]=>[1, 2, 0],
      [5, 0]=>[2, 1, 0], [4, 2]=>[0, 2, 1], [2, 5]=>[2, 0, 1],
      [1, 3]=>[2, 1, 0], [0, 1]=>[0, 2, 1], [5, 5]=>[0, 1, 2]}
  ]
  @cycles = [
    [[]],
    [[]],
    [[], [[0, 1]]],
    [[], [[1, 2]], [[0, 1]], [[0, 1, 2]], [[0, 2, 1]], [[0, 2]]],
    [[], [[2, 3]], [[1, 2]], [[1, 2, 3]], [[1, 3, 2]], [[1, 3]],
      [[0, 1]], [[0, 1], [2, 3]], [[0, 1, 2]], [[0, 1, 2, 3]],
      [[0, 1, 3, 2]], [[0, 1, 3]], [[0, 2, 1]], [[0, 2, 3, 1]],
      [[0, 2]], [[0, 2, 3]], [[0, 2], [1, 3]], [[0, 2, 1, 3]],
      [[0, 3, 2, 1]], [[0, 3, 1]], [[0, 3, 2]], [[0, 3]],
      [[0, 3, 1, 2]], [[0, 3], [1, 2]]]
  ]
  @signum = [
    [1],
    [1],
    [1, -1],
    [1, -1, -1, 1, 1, -1],
    [1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1,
      -1, 1, 1, -1, -1, 1]
  ]
end

#test_compare ⇒ Object 



129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'tests/permutation_test.rb', line 129

def test_compare
  perm1 = Permutation.new(3)
  perm2 = Permutation.new(3)
  perm3 = perm1.dup
  perm4 = Permutation.new(3, 1)
  assert(!perm1.equal?(perm2))
  assert(perm1 == perm2)
  assert(perm1.eql?(perm2))
  assert_equal(0, perm1 <=> perm2)
  assert_equal(perm1.hash, perm2.hash)
  assert(!perm1.equal?(perm3))
  assert(perm1 == perm3)
  assert(perm1.eql?(perm3))
  assert_equal(0, perm1 <=> perm3)
  assert_equal(perm1.hash, perm3.hash)
  assert(!perm1.equal?(perm4))
  assert(perm1 != perm4)
  assert(!perm1.eql?(perm4))
  assert_equal(-1, perm1 <=> perm4)
  assert_equal(1, perm4 <=> perm1)
  assert(perm1 < perm4)
  assert(perm4 > perm1)
  assert(perm1.hash != perm4.hash)
  perms = perm1.to_a
  perms[1..-1].each_with_index do |p, i|
    assert(p > perms[i])
    assert_equal(1, p <=> perms[i])
    assert(perms[i] < p)
    assert_equal(-1, perms[i] <=> p)
  end
end

#test_compose ⇒ Object 



206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 
# File 'tests/permutation_test.rb', line 206

def test_compose
  too_big = Permutation.new(10)
  @perms[0..3].each do |perm|
    elements = perm.to_a
    for i in 0...elements.size
      for j in 0...elements.size
        assert_equal(@products[perm.size][[i, j]],
                     (elements[i].compose(elements[j])).value)
        assert_equal(@products[perm.size][[i, j]],
                     (elements[i] * elements[j]).value)
      end
      assert_raises(ArgumentError) { elements[i] * too_big }
      assert_raises(ArgumentError) { elements[i].compose(too_big) }
    end
  end
end

#test_created ⇒ Object 



87
88
89
90
91
92
93
94
 
# File 'tests/permutation_test.rb', line 87

def test_created
  factorial = 1
  @perms.each_with_index do |p, i|
    assert_equal(i, p.size)
    assert_equal(factorial - 1, p.last)
    factorial *= (i + 1)
  end
end

#test_cycles ⇒ Object 



235
236
237
238
239
240
241
 
# File 'tests/permutation_test.rb', line 235

def test_cycles
  @perms.each_with_index do |perm, i|
    assert_equal(@cycles[i], perm.map { |p| p.cycles })
    assert_equal(perm.to_a,
                 @cycles[i].map { |c| Permutation.from_cycles(c, i) })
  end
end

#test_enumerable ⇒ Object 



171
172
173
174
175
176
177
178
179
180
181
182
 
# File 'tests/permutation_test.rb', line 171

def test_enumerable
  @perms.each_with_index do |perm, i|
    assert_equal(@perms_each[i], perm.map { |x| x.value })
  end
  @perms.each_with_index do |perm, i|
    ary = []
    old_rank = perm.rank
    perm.each! { |x| ary << x.value }
    assert_equal(@perms_each[i], ary)
    assert_equal(old_rank, perm.rank)
  end
end

#test_for_mapping_basic ⇒ Object 



263
264
265
266
267
268
 
# File 'tests/permutation_test.rb', line 263

def test_for_mapping_basic
  a = (0..99).to_a
  b = a.shuffle
  ref = Permutation.from_value(b)
  assert_equal(Permutation.for_mapping(a, b), ref)
end

#test_for_mapping_random ⇒ Object 



271
272
273
274
275
276
277
278
279
280
 
# File 'tests/permutation_test.rb', line 271

def test_for_mapping_random
  a = ("A".."Z").to_a
  b = a.shuffle
  p = Permutation.for_mapping(a, b)
  assert_equal(p.project(a), b)
  3.times { a.push("Z") }
  b = a.shuffle
  p = Permutation.for_mapping(a, b)
  assert_equal(p.project(a), b)
end

#test_for_mappings_random_objects ⇒ Object 



282
283
284
285
286
287
 
# File 'tests/permutation_test.rb', line 282

def test_for_mappings_random_objects
  a = [Array.new, Hash.new, nil, 0]
  b = [Hash.new, nil, Array.new, 0]
  p = Permutation.for_mapping(a, b)
  assert_equal(p.value, [1, 2, 0, 3])
end

#test_identity ⇒ Object 



254
255
256
257
258
259
260
261
 
# File 'tests/permutation_test.rb', line 254

def test_identity
  a = ("A".."Z").to_a
  b = a.shuffle
  p = Permutation.for_mapping(a, b)
  assert_equal(Permutation.identity(p.size), Permutation.from_value((0..25).to_a))
  assert_equal(Permutation.identity(p.size), p.identity)
  assert_equal(p * -p, p.identity)
end

#test_invert ⇒ Object 



223
224
225
226
227
228
229
230
231
232
233
 
# File 'tests/permutation_test.rb', line 223

def test_invert
  @perms.each do |perm|
    id = perm
    perm.each do |p|
      assert_equal(id.value, (p * p.invert).value)
      assert_equal(id, p * p.invert)
      assert_equal(id.value, (p * -p).value)
      assert_equal(id, p * -p)
    end
  end
end

#test_mapping_for_non_arrays ⇒ Object 



289
290
291
292
293
294
 
# File 'tests/permutation_test.rb', line 289

def test_mapping_for_non_arrays
  a = "abcdef"
  b = a.split('').shuffle * ''
  p = Permutation.for_mapping(a, b)
  assert_equal(p.project(a), b)
end

#test_next ⇒ Object 



184
185
186
187
188
189
190
191
192
 
# File 'tests/permutation_test.rb', line 184

def test_next
  @next_pred.each do |before, after|
    beforep = Permutation.from_value(before)
    afterp = Permutation.from_value(after)
    assert_equal(afterp, beforep.next)
    assert_equal(beforep, afterp.pred)
    assert_equal(afterp, beforep.succ)
  end
end

#test_power ⇒ Object 



296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
 
# File 'tests/permutation_test.rb', line 296

def test_power
  4.times do |i|
    perms = Permutation.new(i)
    perms.each do |perm|
      assert_equal(perm * perm, perm ** 2)
      assert_equal(perm * perm * perm, perm ** 3)
      assert_equal(perm * perm * perm * perm, perm ** 4)
      assert_equal(perm, perm ** 1)
      assert_equal(Permutation.identity(i), perm ** 0)
      assert_equal(-perm, perm ** -1)
      assert_equal(-perm * -perm, perm ** -2)
    end
  end
  assert_raise(TypeError) { Permutation.new(4).random ** 'nix' }
end

#test_project ⇒ Object 



194
195
196
197
198
199
200
201
202
203
204
 
# File 'tests/permutation_test.rb', line 194

def test_project
  too_big = Array.new(10)
  @perms.each_with_index do |perms, i|
    assert_equal(@projected[i], perms.map { |p| p.project(@projected[i][0]) })
    assert_raises(ArgumentError) { perms.project }
    assert_raises(ArgumentError) { perms.project(too_big) }
  end
  @perms_collections.each_with_index do |perms, i|
    assert_equal(@projected[i], perms.map { |p| p.project })
  end
end

#test_random ⇒ Object 



161
162
163
164
165
166
167
168
169
 
# File 'tests/permutation_test.rb', line 161

def test_random
  @perms_each.each_with_index do |perms, i|
    perm = Permutation.new(i)
    until perms.empty?
      deleted = perms.delete perm.random.value
      deleted and assert true
    end
  end
end

#test_rank_assign ⇒ Object 



96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'tests/permutation_test.rb', line 96

def test_rank_assign
  perm = Permutation.new(3)
  perms = [
    [0, 1, 2],
    [0, 2, 1],
    [1, 0, 2],
    [1, 2, 0],
    [2, 0, 1],
    [2, 1, 0],
    [0, 1, 2],
  ]
  (-12...-6).each do |i|
    perm.rank = i
    assert_equal(perms[i + 12], perm.value)
  end
  (-6...0).each do |i|
    perm.rank = i
    assert_equal(perms[i + 6], perm.value)
  end
  (0..6).each do |i|
    perm.rank = i
    assert_equal(perms[i], perm.value)
  end
  (6..12).each do |i|
    perm.rank = i
    assert_equal(perms[i - 6], perm.value)
  end
  (12..17).each do |i|
    perm.rank = i
    assert_equal(perms[i - 12], perm.value)
  end
end

#test_signum ⇒ Object 



243
244
245
246
247
248
249
250
251
252
 
# File 'tests/permutation_test.rb', line 243

def test_signum
  @perms.each_with_index do |perm, i|
    assert_equal(@signum[i], perm.map { |p| p.signum })
    assert_equal(@signum[i], perm.map { |p| p.sgn })
    assert_equal(@signum[i].map { |x| x == 1 },
                 perm.map { |p| p.even? })
    assert_equal(@signum[i].map { |x| x == -1 },
                 perm.map { |p| p.odd? })
  end
end