5月 262012
 

■環境
Groovy Version: 1.8.6 JVM: 1.7.0_02 Vendor: Oracle Corporation OS: Windows 7

■combination.groovy


def combination(List list, int n) {
  if (n == 1) return list.collect{[it]}
  
  def rList = []
  (list.size()-1).times { int i ->
    rList += combination(list[i+1..-1], n-1).collect{[list[i]]+it}
  }
  return rList
}


Object a = "a"
Object b = ["list"]
Object c = 3
Object d = 1.0
Object e = false
Object f = ["key":"value"]
Object g = new BigDecimal("100")

def list5 = [a, b, c, d, e]
assert combination(list5, 0) == []
assert combination(list5, 1) == [[a], [b], [c], [d], [e]]
assert combination(list5, 2) == [[a, b], [a, c], [a, d], [a, e],
                                 [b, c], [b, d], [b, e],
                                 [c, d], [c, e],
                                 [d, e]]
assert combination(list5, 3) == [[a, b, c], [a, b, d], [a, b, e],
                                 [a, c, d], [a, c, e], [a, d, e],
                                 [b, c, d], [b, c, e], [b, d, e],
                                 [c, d, e]]
assert combination(list5, 4) == [[a, b, c, d], [a, b, c, e],
                                 [a, b, d, e], [a, c, d, e],
                                 [b, c, d, e]]
assert combination(list5, 5) == [[a, b, c, d, e]]
assert combination(list5, 6) == []
assert list5 == [a, b, c, d, e]

def list6b = [a, b, c, d, e, a]
def list6B = list6b.unique(false)
assert combination(list6B, 0) == []
assert combination(list6B, 1) == [[a], [b], [c], [d], [e]]
assert combination(list6B, 2) == [[a, b], [a, c], [a, d], [a, e],
                                  [b, c], [b, d], [b, e],
                                  [c, d], [c, e],
                                  [d, e]]
assert combination(list6B, 3) == [[a, b, c], [a, b, d], [a, b, e],
                                  [a, c, d], [a, c, e], [a, d, e],
                                  [b, c, d], [b, c, e], [b, d, e],
                                  [c, d, e]]
assert combination(list6B, 4) == [[a, b, c, d], [a, b, c, e],
                                  [a, b, d, e], [a, c, d, e],
                                  [b, c, d, e]]
assert combination(list6B, 5) == [[a, b, c, d, e]]
assert combination(list6B, 6) == []
assert list6b == [a, b, c, d, e, a]

def list6C = [a, b, c, d, e, a]
assert combination(list6C, 0) == []
assert combination(list6C, 1) == [[a], [b], [c], [d], [e], [a]]
assert combination(list6C, 2) == [[a, b], [a, c], [a, d], [a, e], [a, a],
                                  [b, c], [b, d], [b, e], [b, a],
                                  [c, d], [c, e], [c, a],
                                  [d, e], [d, a],
                                  [e, a]]
assert combination(list6C, 3) == [[a, b, c], [a, b, d], [a, b, e], [a, b, a],
                                  [a, c, d], [a, c, e], [a, c, a], [a, d, e],
                                  [a, d, a], [a, e, a],
                                  [b, c, d], [b, c, e], [b, c, a], [b, d, e],
                                  [b, d, a], [b, e, a],
                                  [c, d, e], [c, d, a], [c, e, a],
                                  [d, e, a]]
assert combination(list6C, 4) == [[a, b, c, d], [a, b, c, e], [a, b, c, a],
                                  [a, b, d, e], [a, b, d, a], [a, b, e, a],
                                  [a, c, d, e], [a, c, d, a], [a, c, e, a],
                                  [a, d, e, a],
                                  [b, c, d, e], [b, c, d, a], [b, c, e, a],
                                  [b, d, e, a],
                                  [c, d, e, a]]
assert combination(list6C, 5) == [[a, b, c, d, e], [a, b, c, d, a], [a, b, c, e, a],
                                  [a, b, d, e, a], [a, c, d, e, a], [b, c, d, e, a]]
assert combination(list6C, 6) == [[a, b, c, d, e, a]]
assert combination(list6C, 7) == []
assert list6C == [a, b, c, d, e, a]

def list6 = [a, b, c, d, e, f]
assert combination(list6, 0) == []
assert combination(list6, 1) == [[a], [b], [c], [d], [e], [f]]
assert combination(list6, 2) == [[a, b], [a, c], [a, d], [a, e], [a, f],
                                 [b, c], [b, d], [b, e], [b, f],
                                 [c, d], [c, e], [c, f],
                                 [d, e], [d, f],
                                 [e, f]]
assert combination(list6, 3) == [[a, b, c], [a, b, d], [a, b, e], [a, b, f],
                                 [a, c, d], [a, c, e], [a, c, f], [a, d, e],
                                 [a, d, f], [a, e, f],
                                 [b, c, d], [b, c, e], [b, c, f], [b, d, e],
                                 [b, d, f], [b, e, f],
                                 [c, d, e], [c, d, f], [c, e, f],
                                 [d, e, f]]
assert combination(list6, 4) == [[a, b, c, d], [a, b, c, e], [a, b, c, f],
                                 [a, b, d, e], [a, b, d, f], [a, b, e, f],
                                 [a, c, d, e], [a, c, d, f], [a, c, e, f],
                                 [a, d, e, f],
                                 [b, c, d, e], [b, c, d, f], [b, c, e, f],
                                 [b, d, e, f],
                                 [c, d, e, f]]
assert combination(list6, 5) == [[a, b, c, d, e], [a, b, c, d, f], [a, b, c, e, f],
                                 [a, b, d, e, f], [a, c, d, e, f], [b, c, d, e, f]]
assert combination(list6, 6) == [[a, b, c, d, e, f]]
assert combination(list6, 7) == []
assert list6 == [a, b, c, d, e, f]

def list7 = [a, b, c, d, e, f, g]
assert combination(list7, 0) == []
assert combination(list7, 1) == [[a], [b], [c], [d], [e], [f], [g]]
assert combination(list7, 2) == [[a, b], [a, c], [a, d], [a, e], [a, f], [a, g],
                                 [b, c], [b, d], [b, e], [b, f], [b, g],
                                 [c, d], [c, e], [c, f], [c, g],
                                 [d, e], [d, f], [d, g],
                                 [e, f], [e, g],
                                 [f, g]]
assert combination(list7, 3) == [[a, b, c], [a, b, d], [a, b, e], [a, b, f],
                                 [a, b, g], [a, c, d], [a, c, e], [a, c, f],
                                 [a, c, g], [a, d, e], [a, d, f], [a, d, g],
                                 [a, e, f], [a, e, g], [a, f, g],
                                 [b, c, d], [b, c, e], [b, c, f], [b, c, g],
                                 [b, d, e], [b, d, f], [b, d, g], [b, e, f],
                                 [b, e, g], [b, f, g],
                                 [c, d, e], [c, d, f], [c, d, g], [c, e, f],
                                 [c, e, g], [c, f, g],
                                 [d, e, f], [d, e, g], [d, f, g],
                                 [e, f, g]]
assert combination(list7, 4) == [[a, b, c, d], [a, b, c, e], [a, b, c, f],
                                 [a, b, c, g], [a, b, d, e], [a, b, d, f],
                                 [a, b, d, g], [a, b, e, f], [a, b, e, g],
                                 [a, b, f, g], [a, c, d, e], [a, c, d, f],
                                 [a, c, d, g], [a, c, e, f], [a, c, e, g],
                                 [a, c, f, g], [a, d, e, f], [a, d, e, g],
                                 [a, d, f, g], [a, e, f, g],
                                 [b, c, d, e], [b, c, d, f], [b, c, d, g],
                                 [b, c, e, f], [b, c, e, g], [b, c, f, g],
                                 [b, d, e, f], [b, d, e, g], [b, d, f, g],
                                 [b, e, f, g],
                                 [c, d, e, f], [c, d, e, g], [c, d, f, g],
                                 [c, e, f, g],
                                 [d, e, f, g]]
assert combination(list7, 5) == [[a, b, c, d, e], [a, b, c, d, f], [a, b, c, d, g],
                                 [a, b, c, e, f], [a, b, c, e, g], [a, b, c, f, g],
                                 [a, b, d, e, f], [a, b, d, e, g], [a, b, d, f, g],
                                 [a, b, e, f, g], [a, c, d, e, f], [a, c, d, e, g],
                                 [a, c, d, f, g], [a, c, e, f, g], [a, d, e, f, g],
                                 [b, c, d, e, f], [b, c, d, e, g], [b, c, d, f, g],
                                 [b, c, e, f, g], [b, d, e, f, g],
                                 [c, d, e, f, g]]
assert combination(list7, 6) == [[a, b, c, d, e, f], [a, b, c, d, e, g],
                                 [a, b, c, d, f, g], [a, b, c, e, f, g],
                                 [a, b, d, e, f, g], [a, c, d, e, f, g],
                                 [b, c, d, e, f, g]]
assert combination(list7, 7) == [[a, b, c, d, e, f, g]]
assert combination(list7, 8 ) == []
assert list7 == [a, b, c, d, e, f, g]


def list0 = []
assert combination(list0, 0) == []
assert combination(list0, 1) == []
assert combination(list0, 2) == []
assert list0 == []

def list1 = [a]
assert combination(list1, 0) == []
assert combination(list1, 1) == [[a]]
assert combination(list1, 2) == []
assert list1 == [a]

def list2 = [a, b]
assert combination(list2, 0) == []
assert combination(list2, 1) == [[a], [b]]
assert combination(list2, 2) == [[a, b]]
assert combination(list2, 3) == []
assert list2 == [a, b]

def list3 = [a, b, c]
assert combination(list3, 0) == []
assert combination(list3, 1) == [[a], [b], [c]]
assert combination(list3, 2) == [[a, b], [a, c],
                                 [b, c]]
assert combination(list3, 3) == [[a, b, c]]
assert combination(list3, 4) == []
assert list3 == [a, b, c]

def list4 = [a, b, c, d]
assert combination(list4, 0) == []
assert combination(list4, 1) == [[a], [b], [c], [d]]
assert combination(list4, 2) == [[a, b], [a, c], [a, d],
                                 [b, c], [b, d],
                                 [c, d]]
assert combination(list4, 3) == [[a, b, c], [a, b, d], [a, c, d],
                                 [b, c, d]]
assert combination(list4, 4) == [[a, b, c, d]]
assert combination(list4, 5) == []
assert list4 == [a, b, c, d]

/*
// 試行錯誤の残骸 orz..

def combination(List list, int n) {
  // def listP = new ArrayList(list)
  def listP = list.unique(false)
  def rList = []
  if (n == 1) return listP.collect{[it]}
  while (listP.size() > 0) {
    def head = listP.remove(0)
    combination(listP, n-1).each{ rList << [head]+it }
  }
  return rList
}

// 試行錯誤の残骸 orz.

def combination(List listIn, int n){
    // 非破壊的に"重複削除したList"を生成しセット
    List list = listIn.unique(false)
    List rList = []
    while(n>0 && list.size()>0){
        def temp = combinationPart([], [], new ArrayList(list), n)
        def object = list.remove(0)
        temp.findAll{ it?.getAt(0) == object }.each { rList << it }
        if(list.size()<n) break
    }
    return rList
}

private def combinationPart(List rList, List listTemp, List listIn, int n){
    def combinationPartInner = { List rListParam, List listInParam, int num ->
        while(listInParam.size()>0){
            combinationPart([], [], new ArrayList(listInParam), num)
                .each{ rListParam << it }
            listInParam.remove(0)
            if(num==1) break
        }
        return rListParam
    }

    if ( listIn.size() >= n ) {
        listTemp << listIn.remove(0)
        if ( listTemp.size() == n ) {
            if (!rList.contains(listTemp)){
                if (rList?.size()==0 || listTemp?.size()==1) {
                    rList << listTemp
                }
                if (rList?.size()>0 && listTemp?.size()>1){
                    if ( rList?.getAt(0)?.getAt(0) == listTemp?.getAt(0)) {
                        rList << listTemp
                    }
                }
            }
            listTemp =  new ArrayList(listTemp)
            listTemp.remove(0)
        } else if (n!=1) {
            combinationPartInner([], listIn, n-1).each {
                rList << ( new ArrayList(listTemp) + it )
            }
        }
        rList = combinationPart(rList, listTemp, listIn, n)
    }
    return rList
}
*/

Sorry, the comment form is closed at this time.