Class: Statsample::Permutation

Inherits:
Object
  • Object
show all
Defined in:
lib/statsample/permutation.rb

Overview

Permutation class systematically generates all permutations of elements on an array, using Dijkstra algorithm (1997).

As argument, you could use

  • Number of elements: an array with numbers from 0 to n-1 will be used

  • Array: if ordered, you obtain permutations on lexicographic order

    you can repeat elements, if you will.

Use:
perm=Statsample::Permutation.new(3)
perm.permutations
=> [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]
perm=Statsample::Permutation.new([0,0,1,1])
=> [[0,0,1,1],[0,1,0,1],[0,1,1,0],[1,0,0,1],[1,0,1,0],[1,1,0,0]]

Reference:

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(v) ⇒ Permutation

Returns a new instance of Permutation.



21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/statsample/permutation.rb', line 21

def initialize(v)
  if v.is_a? Numeric
    @original=(0...v.to_i).to_a
    @permutation_number=factorial(v)
  else
    @original=v
    calculate_max_iterations_from_array
  end
  @n=@original.size
  reset
end

Instance Attribute Details

#permutation_number ⇒ Object (readonly)

Returns the value of attribute permutation_number.



20
21
22
 
# File 'lib/statsample/permutation.rb', line 20

def permutation_number
  @permutation_number
end

Instance Method Details

#calculate_max_iterations_from_array ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/statsample/permutation.rb', line 32

def calculate_max_iterations_from_array
  if @original.respond_to? :frequencies
    freq=@original.frequencies
  else
    freq=@original.to_vector.frequencies
  end
  if freq.length==@original.size
    @permutation_number=factorial(@original.size)
  else
    numerator=factorial(@original.size)
    denominator=freq.inject(1) {|a,v|
      a*factorial(v[1])
    }
    @permutation_number=numerator/denominator
  end
end

#each ⇒ Object 



55
56
57
58
59
60
 
# File 'lib/statsample/permutation.rb', line 55

def each
  reset
  @permutation_number.times do
    yield next_value
  end
end

#factorial(n) ⇒ Object 



48
49
50
 
# File 'lib/statsample/permutation.rb', line 48

def factorial (n)
  (1..n).inject(1){|a,v| a*v}
end

#next_value ⇒ Object 



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/statsample/permutation.rb', line 66

def next_value
  prev=@data.dup
  i = @n-1
  while @data[i-1] >= @data[i]
    #return false if i<0 
    i=i-1
  end
  j=@n
  while @data[j-1] <= @data[i-1]
    j=j-1
  end
  # swap values at positions (i-1) and (j-1)
  swap(i-1, j-1);    
  
  i+=1
  j = @n
  
  while (i < j)
    swap(i-1, j-1);
    i+=1;
    j-=1;
    sprintf("%d %d",i,j)
  end
  prev
end

#permutations ⇒ Object 



61
62
63
64
65
 
# File 'lib/statsample/permutation.rb', line 61

def permutations
  a=Array.new
  each {|c| a.push(c)}
  a
end

#reset ⇒ Object 



51
52
53
54
 
# File 'lib/statsample/permutation.rb', line 51

def reset
  @iterations=0
  @data=@original.dup
end

#swap(i, j) ⇒ Object 



91
92
93
94
95
 
# File 'lib/statsample/permutation.rb', line 91

def swap(i,j)
  tmp=@data[i]
  @data[i]=@data[j]
  @data[j]=tmp
end