Module: CodeCook::Enumeration

Defined in:
手写代码必备手册(Ruby版).rb

Overview

第八章 暴力枚举法 暴力枚举法 (brute force enumeration) 又称为暴力搜索法 (Brute-force search),详细定义见 Wikipedia

Class Method Summary (collapse)

Class Method Details

+ (Object) permutation(array = [], i = 0)

8.1.1 全排列 在Ruby中可以通过Array.permutation实现

Parameters:

  • array (Array) (defaults to: []) —

    需要排列的数组

Returns:

  • 打印出排列后的结果



440
441
442
443
444
445
446
447
448
449
450
 
# File '手写代码必备手册(Ruby版).rb', line 440

def permutation(array=[], i=0)
    if i == array.size
        p array
    else
        (i..array.size-1).each do |k|
            array[i], array[k] = array[k], array[i]
            permutation(array, i + 1)
            array[i], array[k] = array[k], array[i]
        end
    end
end

+ (Object) subset1(array, out = [], ed)

8.2.1 增量构造法



455
456
457
458
459
460
461
 
# File '手写代码必备手册(Ruby版).rb', line 455

def subset1(array, out=[], ed)
    (ed..array.size-1).each do |i|
        out << array[i]
        puts out.join(' ')
        subsete1(array, out, i+1)
    end
end

+ (Object) subset3(array)

8.2.3 二进制法

Parameters:

  • array (Array) —

    集合



466
467
468
469
470
471
472
473
474
 
# File '手写代码必备手册(Ruby版).rb', line 466

def subset3(array)
    n = array.size
    (1..(1 << n)).each do |i|
        (0..n).each do |j|
            print "#{array[j]} " if (i & (1 << j)) != 0
        end
        puts ''
    end
end