[Bug #3708] Array#permutation $B$,$*$+$7$J7k2L$rJV$9(B

[Shumpei_A]

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”
e$B$@$H@5$7$/F0$-$^$9e(B

[Shumpei_A]

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

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

e$B$@$H@5$7$/F0$-$^$9e(B
ary_make_shared e$B4X?t$r0J2<$N$h$&$K=$@5$9$k$H@5>o$KF0:n$7$^$9!#e(B

diff --git a/array.c b/array.c
index 51d3ad2…ea4fe43 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 e8edcc2…f2d723f 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

Ruby 逆引きレシピ すぐに美味しいサンプル&amp;テクニック 232 (PROGRAMMER’S RECIPE) | 島田 浩二, 設樂 洋爾, 村田...

E-mail: [email protected]
twitter: http://twitter.com/mrkn/
blog: ドレッシングのような

[Shumpei_A]

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”
|> e$B$@$H@5$7$/F0$-$^$9e(B
|
|
|ary_make_shared e$B4X?t$r0J2<$N$h$&$K=$@5$9$k$H@5>o$KF0:n$7$^$9!#e(B
|
|diff --git a/array.c b/array.c
|index 51d3ad2…ea4fe43 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

[Shumpei_A]

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

e$B$J$+$@$5$s$Ke(B ary_make_shared_copy
e$B$r65$($F$b$i$C$?$N$G!"$b$&0lEY=$@50F$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 51d3ad2…bca7956 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

Ruby 逆引きレシピ すぐに美味しいサンプル&amp;テクニック 232 (PROGRAMMER’S RECIPE) | 島田 浩二, 設樂 洋爾, 村田...

E-mail: [email protected]
twitter: http://twitter.com/mrkn/
blog: ドレッシングのような