majiang

def hungarian(cost):
    '''solves assignment method on a bipartite graph.

description: http://en.wikipedia.org/wiki/Hungarian_algorithm#The_algorithm_in_terms_of_bipartite_graphs

S: n worker vertices
T: n job vertices

input:
    cost[i][j] = cost of edges from S[i] to T[j]

majiang

module functionstyle;

import std.stdio;

T delegate(T) zero(T)(T delegate(T) f)
{
    T ret(T x)
    {
        return x;
    }

majiang

module deque;

import core.exception : RangeError;

struct Deque(T)
{
private:

    T[] deque;
    size_t begin, end; // inclusive lower and exclusive upper bound

majiang

8 elements in commutator subgroup:
+0-1+2-3
+0-1-2+3
+0+1-2-3
+0+1+2+3
-0-1-2-3
-0+1+2-3
-0+1-2+3
-0-1+2+3
8 elements in quotient group:

majiang

[(0, 0), (2, 0), (3, 0), (1, 1), (2, 1), (3, 1), (1, 2), (2, 2)]
|XX  |
|XXX |
| XX |
|X   |

[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (3, 1), (0, 2), (3, 2)]
| XX |
|X   |
|XX  |

majiang

(2)
[(0, 0), (2, 0), (3, 0), (1, 1), (2, 1), (3, 1), (1, 2), (2, 2)]
|XX  |    |XX  |    |  XX|    |XXXX|    |    |
|XXX | AF |XXX | cp |   X| AF |XXXX| cp |    |
| XX |--->| XX |--->|X  X|--->|XXXX|--->|    |
|X   |    |X   |    | XXX|    |XXXX|    |    |

[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (3, 1), (0, 2), (3, 2)]
| XX |    | XX |    |X  X|    |XXXX|    |    |
|X   | AF |X   | cp | XXX| AF |XXXX| cp |    |

majiang

there are 3 equivalence class
32 subsets of size 8{
    |  X |
    | X  |
    |XX X|
    |XXX |

    |X   |
    |   X|
    |XX X|

majiang

/**
Berlekamp-Massey Algorithm の実装
東京大学理学部数学科 数学講究XB
2012/05/15 松本眞教授「互除法と Berlekamp-Massey 法」
の講義ノートによる
*/
module BerlekampMassey;

alias bool B; /// bool 配列を多用するためエイリアスにしたが、本当はこうするのはよくない。
import std.algorithm;

majiang

Polynomial test:
  x^4 + x^3 + x^2 + x^1 + x^0 = 11111
  x^4 + x^3 + x^2 + x^1 = 11110
  x^2 + x^1 + x^0 = 111
  0x^2 + x^1 + x^0 = 11
  11 + 101 = 110
  11 + 10010 = 10001
  101 + 10010 = 10111
  11 * 101 = 1111
  11 * 10010 = 110110

majiang

Public Function rank (m As ULong(,)) As Integer
    ' m は size * size 行列
    Dim mi As Integer = size - 1
    For i As Integer = 0 To size - 1
        Dim pj As Integer
        pj = -1
        While pj < 0
            For j As Integer = 0 To size - 1
                If m(i, j) Then
                    pj = j