Name: simulation/test/tt_permutationtester.rb 
1:
require 'pp'
2:
require 'rubygems'
3:
 
4:
# Damerau-Levenshtein distance with adjacent transpositions
5:
# takes two arrays as input, array elements should have ::== and be comparable
6:
# more info and sample implementation in other languages:
7:
#  * http://dl.acm.org/citation.cfm?id=363994
8:
#  * http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
9:
def distance(source,target)
10:
  combo = source.length + target.length
11:
 
12:
  score = Array.new(source.length+2)do |i|
13:
    Array.new(target.length+2) do |j|
14:
      i == 0 || j == 0 ? combo : i == 1 ? j -1 : j == 1 ? i - 1 : 0
15:
    end
16:
  end
17:
 
18:
  sd = Hash[(source + target).collect { |e| [e, 0] }]
19:
 
20:
  1.upto(source.length) do |i|
21:
    db = 0
22:
    1.upto(target.length) do |j|
23:
      it = sd[target[j-1]]
24:
      jt = db
25:
 
26:
      if (source[i-1] == target[j-1])
27:
        score[i+1][j+1] = score[i][j]
28:
        db = j
29:
      else
30:
        score[i+1][j+1] = [score[i][j],[score[i+1][j],score[i][j+1]].min].min + 1
31:
      end
32:
 
33:
      score[i+1][j+1] = [score[i+1][j+1],score[it][jt]+(i-it-1)+1+(j-jt-1)].min
34:
    end
35:
 
36:
    sd[source[i-1]] = i
37:
  end
38:
 
39:
  score[source.length+1][target.length+1]
40:
end
41:
 
42:
def move?(branches,a,b)
43:
  branches.each do |branch|
44:
    return false if branch.include?(a) && branch.include?(b) && branch.index(a) + 1 == branch.index(b)
45:
  end
46:
  true
47:
end
48:
 
49:
def mix(branches)
50:
  permutations = [ branches.flatten ]
51:
  permutations_index = -1
52:
 
53:
  begin
54:
    permutations_index += 1
55:
    base = permutations[permutations_index].dup
56:
    counter = 0
57:
    while counter < base.length-1
58:
      break if counter == base.length
59:
      e1 = base[counter]
60:
      e2 = base[counter+1]
61:
      if move?(branches, e1, e2)
62:
        base[counter], base[counter+1] = base[counter+1], base[counter]
63:
        permutations << base.dup
64:
      end
65:
      counter += 1
66:
    end
67:
    permutations = permutations.uniq
68:
  end while permutations_index + 1 < permutations.length
69:
 
70:
  permutations
71:
end
72:
 
73:
def std_cases(branches)
74:
  run = []
75:
  max = branches.max_by{ |b| b.length }.length
76:
  0.upto(max-1) do |col|
77:
    column = []
78:
    branches.each do |branch|
79:
      column << branch[col]
80:
    end
81:
    if run.empty?
82:
      run = column.permutation.to_a
83:
    else
84:
      tmp = []
85:
      column.permutation.each do |per|
86:
        run.each do |tper|
87:
          tmp << tper + per
88:
        end
89:
      end
90:
      run = tmp
91:
    end
92:
  end
93:
  run
94:
end
95:
 
96:
# testset = [[:a,:b], [:c,:d], [:e,:f], [:g,:h]]
97:
# testset = [[:a,:b], [:c,:d], [:g,:h]]
98:
# testset = [[:a,:b], [:c,:d]]
99:
# testset = [[:a,:b,:c], [:d,:e], [:f,:g]]
100:
# testset = [[:a,:b, :c], [:d,:e,:f], [:g,:h,:i]]
101:
 
102:
# testset = [[:a,:b], [:d,:e], [:f,:g]]
103:
#testset = [[:m,:n], [:m,:n]]
104:
#testset = [[:m,:n], [:m,:n], [:m, :n]]
105:
testset = [(1..10).to_a, (1..10).to_a]
106:
#stdcases = std_cases testset
107:
#stdcases.uniq!
108:
 
109:
result = mix testset
110:
pp result
111:
exit
112:
 
113:
dists = result.collect do |res|
114:
  stdcases.collect do |std|
115:
    distance(std,res)
116:
  end.min
117:
end
118:
maxdist = dists.max
119:
 
120:
puts "Testset:"
121:
testset.each do |ts|
122:
  puts "  Branch: #{ts.inspect}"
123:
end
124:
puts "Resulting Traces:"
125:
 
126:
possiblepieces = (1.0 - (1.0 / result.length)) / maxdist
127:
result.each_with_index do |res,index|
128:
  puts "#{res.inspect} #{dists[index]} #{1 - (possiblepieces * dists[index])}"
129:
end
130:
 
131:
puts "Number of default traces: #{stdcases.length}"
132:
puts "Total number of traces #{result.length}"