[Bug #3708] Array#permutation がおかしな結果を返す

Bug #3708: Array#permutation e$B$,$*$+$7$J7k2L$rJV$9e(B
http://redmine.ruby-lang.org/issues/show/3708

e$B5/I<<Te(B: Shumpei A.
e$B%9%F!<%?%9e(B: Open, e$BM%@hEYe(B: Normal
ruby -v: ruby 1.9.3dev (2010-08-18 trunk 29024) [x86_64-darwin10.4.0]

Array#permutatione$B$N7k2L$K!$G[Ns$K4^$^$l$F$$$J$$$O$:$NCM$,F~$C$F$$$^$9e(B

% ./ruby_head -e p [0,1,2,3,4][1,4].permutation.to_a
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2],
[0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0],
[1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3],
[2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1],
[3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]

[0,1,2,3,4][1,4] e$B$Oe(B [1, 2, 3, 4]
e$B$J$N$Ge(B0e$B$O4^$^$l$J$$$O$:$G$9!%e(B

% ./ruby_head -e p [0,1,2,3][1,3].permutation.to_a
[email protected][email protected]$7$/F0$-$^$9e(B

e$B$`$i$?$G$9!#e(B

On 2010/08/18, at 16:33, Shumpei A. wrote:

[email protected][email protected]$7$/F0$-$^$9e(B
ary_make_shared e$B4X?t$r0J2<$N$h$&[email protected][email protected]>o$KF0:n$7$^$9!#e(B

diff --git a/array.c b/array.c
index 51d3ad2ea4fe43 100644
a/array.c
+++ b/array.c
@@ -409,10 +409,7 @@ static VALUE
ary_make_shared(VALUE ary)
{
assert(!ARY_EMBED_P(ary));

  • if (ARY_SHARED_P(ary)) {
  •   return ARY_SHARED(ary);
    
  • }
  • else if (ARY_SHARED_ROOT_P(ary)) {
  • if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {
    return ary;
    }
    else if (OBJ_FROZEN(ary)) {
    diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb
    index e8edcc2f2d723f 100644
    a/test/ruby/test_array.rb
    +++ b/test/ruby/test_array.rb
    @@ -1549,6 +1549,9 @@ class TestArray < Test::Unit::TestCase
    a.permutation {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
    assert_equal(@cls[9, 8, 7, 6], a)
    assert_equal(@cls[1, 2, 3, 4].permutation.to_a, b)
  • bug3708 = [ruby-dev:42067]
  • assert_equal(b, @cls[0, 1, 2, 3, 4][1, 4].permutation.to_a,
    bug3708)
    end

def test_repeated_permutation


Kenta M.
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

e$BK$r=q$-$^$7$?e(B!!
e$B!Xe(BRuby e$B5U0z$-%l%7%T!Ye(B
http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: [email protected]
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message Re: [ruby-dev:42068] Re: [Bug #3708] Array#permutation
e$B$,$*$+$7$J7k2L$rJV$9e(B
on Wed, 18 Aug 2010 18:16:13 +0900, Kenta M. [email protected]
writes:

|On 2010/08/18, at 16:33, Shumpei A. wrote:
|
|> Array#permutatione$B$N7k2L$K!$G[Ns$K4^$^$l$F$$$J$$$O$:$NCM$,F~$C$F$$$^$9e(B
|>
|> % ./ruby_head -e p [0,1,2,3,4][1,4].permutation.to_a
|> [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
|>
|>
|> [0,1,2,3,4][1,4] e$B$Oe(B [1, 2, 3, 4] e$B$J$N$Ge(B0e$B$O4^$^$l$J$$$O$:$G$9!%e(B
|>
|>
|> % ./ruby_head -e p [0,1,2,3][1,3].permutation.to_a
|> [email protected][email protected]$7$/F0$-$^$9e(B
|
|
|ary_make_shared e$B4X?t$r0J2<$N$h$&[email protected][email protected]>o$KF0:n$7$^$9!#e(B
|
|diff --git a/array.c b/array.c
|index 51d3ad2ea4fe43 100644
| a/array.c
|+++ b/array.c
|@@ -409,10 +409,7 @@ static VALUE
| ary_make_shared(VALUE ary)
| {
| assert(!ARY_EMBED_P(ary));
|- if (ARY_SHARED_P(ary)) {
|- return ARY_SHARED(ary);
|- }
|- else if (ARY_SHARED_ROOT_P(ary)) {
|+ if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {
| return ary;
| }
| else if (OBJ_FROZEN(ary)) {

e$B$J$k$[$I!#%3%_%C%H$7$F2<$5$$!#e(B

e$B$`$i$?$G$9!#e(B

On 2010/08/18, at 18:28, Yukihiro M. wrote:

|- }
|- else if (ARY_SHARED_ROOT_P(ary)) {
|+ if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {
| return ary;
| }
| else if (OBJ_FROZEN(ary)) {

e$B$J$k$[$I!#%3%_%C%H$7$F2<$5$$!#e(B

e$B0lC6$3$l$G%3%_%C%H$7$?$N$G$9$,!e(BSEGV
e$B$,H/@8$9$k$3$H$,$$C$?$?$ae(B revert e$B$7$^$7$?!#e(B

[email protected]$5$s$Ke(B ary_make_shared_copy
e$B$r65$($F$b$i$C$?$N$G!"$b$&[email protected]$rDs<($7$^$9!#e(B
repeated_permutatione$B!"e(Brepeated_combinatione$B!"e(Bproduct
e$B$bBP>]$G$9!#e(B

diff --git a/array.c b/array.c
index 51d3ad2bca7956 100644
a/array.c
+++ b/array.c
@@ -4010,7 +4010,7 @@ rb_ary_permutation(int argc, VALUE *argv, VALUE
ary)
long p = (long)RSTRING_PTR(t0);
volatile VALUE t1 = tmpbuf(n,sizeof(char));
char used = (char)RSTRING_PTR(t1);

  •   VALUE ary0 = ary_make_substitution(ary); /* private defensive 
    

copy of ary */

  •   VALUE ary0 = ary_make_shared_copy(ary); /* private defensive 
    

copy of ary */
RBASIC(ary0)->klass = 0;

    MEMZERO(used, char, n); /* initialize array */

@@ -4180,7 +4180,7 @@ rb_ary_repeated_permutation(VALUE ary, VALUE num)
else { /* this is the general case */
volatile VALUE t0 = tmpbuf(r, sizeof(long));
long p = (long)RSTRING_PTR(t0);

  •   VALUE ary0 = ary_make_substitution(ary); /* private defensive 
    

copy of ary */

  •   VALUE ary0 = ary_make_shared_copy(ary); /* private defensive 
    

copy of ary */
RBASIC(ary0)->klass = 0;

    rpermute0(n, r, p, 0, ary0); /* compute and yield repeated 

permutations */
@@ -4266,7 +4266,7 @@ rb_ary_repeated_combination(VALUE ary, VALUE num)
else {
volatile VALUE t0 = tmpbuf(n, sizeof(long));
long p = (long)RSTRING_PTR(t0);

  •   VALUE ary0 = ary_make_substitution(ary); /* private defensive 
    

copy of ary */

  •   VALUE ary0 = ary_make_shared_copy(ary); /* private defensive 
    

copy of ary */
RBASIC(ary0)->klass = 0;

    rcombinate0(len, n, p, 0, n, ary0); /* compute and yield 

repeated combinations */
@@ -4325,7 +4325,7 @@ rb_ary_product(int argc, VALUE argv, VALUE ary)
/
Make defensive copies of arrays; exit if any is empty */
for (i = 0; i < n; i++) {
if (RARRAY_LEN(arrays[i]) == 0) goto done;

  •       arrays[i] = ary_make_substitution(arrays[i]);
    
  •       arrays[i] = ary_make_shared_copy(arrays[i]);
      }
    
    }
    else {
    a/test/ruby/test_array.rb
    +++ b/test/ruby/test_array.rb
    @@ -1528,6 +1528,10 @@ class TestArray < Test::Unit::TestCase
    acc = [1,2].product(*[o]*10)
    assert_equal([1,2].product([3,4], [3,4], [3,4], [3,4], [3,4],
    [3,4], [3,4], [3,4], [3,4], [3,4]),
    acc)
  • a = []
  • [1, 2].product([0, 1, 2, 3, 4][1, 4]) {|x| a << x }
  • assert(a.all?{|x| !x.include?(0) })
    end

def test_permutation
@@ -1574,6 +1578,9 @@ class TestArray < Test::Unit::TestCase
a.repeated_permutation(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6])
}
assert_equal(@cls[9, 8, 7, 6], a)
assert_equal(@cls[1, 2, 3, 4].repeated_permutation(4).to_a, b)
+

  • a = @cls[0, 1, 2, 3, 4][1, 4].repeated_permutation(2)
  • assert(a.all?{|x| !x.include?(0) })
    end

def test_repeated_combination
@@ -1600,6 +1607,9 @@ class TestArray < Test::Unit::TestCase
a.repeated_combination(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6])
}
assert_equal(@cls[9, 8, 7, 6], a)
assert_equal(@cls[1, 2, 3, 4].repeated_combination(4).to_a, b)
+

  • a = @cls[0, 1, 2, 3, 4][1, 4].repeated_combination(2)
  • assert(a.all?{|x| !x.include?(0) })
    end

def test_take


Kenta M.
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

e$BK$r=q$-$^$7$?e(B!!
e$B!Xe(BRuby e$B5U0z$-%l%7%T!Ye(B
http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: [email protected]
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs