仲間はずれの判定 in xtal DouKaku?

仲間はずれの判定

リストxsが渡されたときに

全部の要素が同じ値である(例：[1, 1, 1, 1])、
一つだけ仲間はずれがある(例：[1, 2, 1, 1, 1])、
その他

を識別する関数を作ってください。また判定後に「全部の要素が同じ値」の場合にはその値、「一つだけ仲間はずれがある」の場合にはその仲間はずれの値と多数派の値を複雑な処理なしに取得できるようにしてください。

型にうるさい言語のために：リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。

追記：リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。

もっとスリム化できそうですがとりあえず。

import java.util.*;
public class NakamaHazure {
    public static void main(String[] args) {
        check(Arrays.asList(1,1,1,1));    // => [1]
        check(Arrays.asList(1,2,1,1,1));    // => [2,1]
        check(Arrays.asList(1,2,2,1,1));    // => []
        check(Arrays.asList(1,2,2,1,3));    // => []
    }
    private static void check(List<Integer> list) {
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> minor = new HashSet<Integer>();;
        Integer major = null;
        for (Integer i : list) {
            if (!set.add(i)) {
                if (major != null && major != i) {
                    System.out.println("[]");
                    return;
                }
                minor.remove(i);
                major = i;
            } else {
                minor.add(i);
            }
        }
        if (set.size() == 1) {
            System.out.println("[" + set.iterator().next() + "]");
        } else if (set.size() == 2) {
            System.out.println("[" + minor.iterator().next() + "," + major + "]");
        } else {
            System.out.println("[]");
        }
    }
}

array_count_values便利ですね。あえて使わないで作ってみる事で便利さを際実感

$a[]= array(1,1,1,1);#1
$a[]= array(1,2,1,1,1);#2
$a[]= array(2,1,2,2);#その他
$a[]= array(1,2,2,2);#その他
$a[]= array(1,1,2,2);#その他
$a[]= array(1,1,2,3);#その他
function check($_array){
    $uniques = sizeof(array_unique($_array));
    switch($uniques){
        case(1):
            return array("仲間"=>array_pop($_array));
        case(2):
            sort($_array);
            #仲間はずれ
            if( $_array[0]!=$_array[1] ){
                return array( "仲間はずれ"=>array_shift($_array),"仲間"=>array_pop($_array) );
            }else if($_array[0]==$_array[1] && $_array[sizeof($_array)-1] != $_array[sizeof($_array)-2] ){
                return array( "仲間はずれ"=>array_pop($_array),"仲間"=>array_shift($_array) );
            }
        default:
            return "その他";
    }


}

foreach( $a as $b ){
    print_r( check($b) ).PHP_EOL;
}

post comment

Posted feedbacks - xtal

辞書などを使った回答はもうずいぶん出ているので違ったアプローチで書いたら、
ずいぶん長くなってしまいました。。

実装はひとつづつ要素を見ながら状態遷移していくものです。
each_classify で状態遷移を観察することができます。

無限列にも適用可能です。
もちろん本当に無限にある場合は「その他」以外では答えを出せないのですが、
無限列の最初の n 個の仲間はずれを判定できます。

Classify: class {
    - _iter;
    - _state: "homo";
    - _majority: null;
    - _minority: null;

    initialize: method(_iter) {}

    + classify: method(n: null) {
        return each_classify(n).to_a.back;
    }

    + each_classify: method(n: null) fiber {
        iter: n ? _iter.take(n) : _iter;
        iter.with_index {|i,it|
            this.(_state)(i, it);
            if (_state == "hetero") {
                break;
            }
        }
    }

    - homo: method(i, it) {
        if (_majority && _majority != it) {
            _minority = it;
            if (i < 2) {
                _state = "quasi_homo0";
                yield ["?", _majority, _minority];
            } else {
                _state = "quasi_homo";
                yield ["quasi_homo", _majority, _minority];
            }
        } else {
            _majority = it;
            yield ["homo", it];
        }
    }

    - quasi_homo0: method(i, it) {
        if (it == _majority || it == _minority) {
            if (it == _minority) {
                _majority, _minority = _minority, _majority;
            }
            yield ["quasi_homo", _majority, _minority];
            _state = "quasi_homo";
        } else {
            hetero(i, it);
        }
    }

    - quasi_homo: method(i, it) {
        if (it == _majority) {
            yield ["quasi_homo", _majority, _minority];
        } else {
            hetero(i, it);
        }
    }

    - hetero: method(i, it) {
        _state = "hetero";
        yield ["hetero", null];
    }
}

Classify([1,1,1,1,1].each).classify.p;    //=> [homo,1]
Classify([1,2,1,1,1].each).classify.p;    //=> [quasi_homo,1,2]
Classify([2,1,1,1,1].each).classify.p;    //=> [quasi_homo,1,2]
Classify([2,2,1,1,1].each).classify.p;    //=> [hetero,null]
Classify([2,4,1,1,1].each).classify.p;    //=> [hetero,null]
Classify([1,2,3,4,5].each).classify.p;    //=> [hetero,null]

Classify([2,1,1,1,3].each).each_classify {
  it.p;
}
//=> [homo,2]
//=> [?,2,1]
//=> [quasi_homo,1,2]
//=> [quasi_homo,1,2]
//=> [hetero,null]

Classify([1,1,3].cycle).classify(5).p;    //=> [quasi_homo,1,3]
Classify([1,1,3].cycle).classify(6).p;    //=> [hetero,null]
Classify([1,2,3].cycle).classify.p;       //=> [hetero,null]

DouKaku?

仲間はずれの判定

Posted feedbacks - xtal

Index

Feed

Other

Link

Pathtraq