Project

General

Profile

Bug #3089 ยป combination_unlimited.diff

marcandre (Marc-Andre Lafortune), 04/04/2010 05:54 AM

View differences:

array.c
3958 3958
    return ary;
3959 3959
}
3960 3960

  
3961
static long
3962
combi_len(long n, long k)
3963
{
3964
    long i, val = 1;
3965

  
3966
    if (k*2 > n) k = n-k;
3967
    if (k == 0) return 1;
3968
    if (k < 0) return 0;
3969
    val = 1;
3970
    for (i=1; i <= k; i++,n--) {
3971
	long m = val;
3972
	val *= n;
3973
	if (val < m) {
3974
	    rb_raise(rb_eRangeError, "too big for combination");
3975
	}
3976
	val /= i;
3977
    }
3978
    return val;
3979
}
3980

  
3981 3961
/*
3982 3962
 *  call-seq:
3983 3963
 *     ary.combination(n) { |c| block }    -> ary
......
4024 4004
    else {
4025 4005
	volatile VALUE t0 = tmpbuf(n+1, sizeof(long));
4026 4006
	long *stack = (long*)RSTRING_PTR(t0);
4027
	long nlen = combi_len(len, n);
4028 4007
	volatile VALUE cc = tmpary(n);
4029 4008
	VALUE *chosen = RARRAY_PTR(cc);
4030 4009
	long lev = 0;
4031 4010

  
4032 4011
	MEMZERO(stack, long, n);
4033 4012
	stack[0] = -1;
4034
	for (i = 0; i < nlen; i++) {
4013
	for (;;) {
4035 4014
	    chosen[lev] = RARRAY_PTR(ary)[stack[lev+1]];
4036 4015
	    for (lev++; lev < n; lev++) {
4037 4016
		chosen[lev] = RARRAY_PTR(ary)[stack[lev+1] = stack[lev]+1];
......
4041 4020
		rb_raise(rb_eRuntimeError, "combination reentered");
4042 4021
	    }
4043 4022
	    do {
4023
		if (lev == 0) goto done;
4044 4024
		stack[lev--]++;
4045
	    } while (lev && (stack[lev+1]+n == len+lev+1));
4025
	    } while (stack[lev+1]+n == len+lev+1);
4046 4026
	}
4027
    done:
4047 4028
	tmpbuf_discard(t0);
4048 4029
	tmpary_discard(cc);
4049 4030
    }
test/ruby/test_array.rb
1842 1842
  end
1843 1843

  
1844 1844
  def test_combination2
1845
    assert_raise(RangeError) do
1846
      (0..100).to_a.combination(50) {}
1845
    assert_nothing_raised do
1846
      (0..100).to_a.combination(50) { break }
1847 1847
    end
1848 1848
  end
1849 1849