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 



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
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
 
# File 'tests/permutation_test.rb', line 8

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 



128
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
 
# File 'tests/permutation_test.rb', line 128

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



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

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 



95
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
 
# File 'tests/permutation_test.rb', line 95

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 



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

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