Backport #3708: Array#permutation がおかしな結果を返す - Backport192 - Ruby Issue Tracking System

Actions

Copy link

Backport #3708

closed

Array#permutation がおかしな結果を返す

Added by akai (Shumpei Akai) over 13 years ago. Updated almost 13 years ago.

Status:

Closed

Assignee:

yugui (Yuki Sonoda)

Description

=begin
Array#permutationの結果に，配列に含まれていないはずの値が入っています

% ./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] は [1, 2, 3, 4] なので0は含まれないはずです．

% ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"
だと正しく動きます
=end

Actions

Copy link

Updated by mrkn (Kenta Murata) over 13 years ago

=begin
むらたです。

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

Array#permutationの結果に，配列に含まれていないはずの値が入っています

% ./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] は [1, 2, 3, 4] なので0は含まれないはずです．

% ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"
だと正しく動きます

ary_make_shared 関数を以下のように修正すると正常に動作します。

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 Murata
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

本を書きました!!
『Ruby 逆引きレシピ』 http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: mrkn@mrkn.jp
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

=end

Actions

Copy link

Updated by matz (Yukihiro Matsumoto) over 13 years ago

=begin
まつもとゆきひろです

In message "Re: [ruby-dev:42068] Re: [Bug #3708] Array#permutation がおかしな結果を返す"
on Wed, 18 Aug 2010 18:16:13 +0900, Kenta Murata muraken@gmail.com writes:

|On 2010/08/18, at 16:33, Shumpei Akai wrote:
|
|> Array#permutationの結果に，配列に含まれていないはずの値が入っています
|>
|> % ./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] は [1, 2, 3, 4] なので0は含まれないはずです．
|>
|>
|> % ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"
|> だと正しく動きます
|
|
|ary_make_shared 関数を以下のように修正すると正常に動作します。
|
|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)) {

なるほど。コミットして下さい。

=end

Actions

Copy link

Updated by mrkn (Kenta Murata) over 13 years ago

Status changed from Open to Closed
% Done changed from 0 to 100

=begin
This issue was solved with changeset r29037.
Shumpei, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end

Actions

Copy link

Updated by mrkn (Kenta Murata) over 13 years ago

Status changed from Closed to Open

=begin
r29037 では SEGV が発生することがあったため、一旦 revert して修正しなおします。

=end

Actions

Copy link

Updated by mrkn (Kenta Murata) over 13 years ago

=begin
むらたです。

On 2010/08/18, at 18:28, Yukihiro Matsumoto wrote:

|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)) {

なるほど。コミットして下さい。

一旦これでコミットしたのですが、SEGV が発生することがあったため revert しました。

なかださんに ary_make_shared_copy を教えてもらったので、もう一度修正案を提示します。
repeated_permutation、repeated_combination、product も対象です。

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 Murata
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

本を書きました!!
『Ruby 逆引きレシピ』 http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: mrkn@mrkn.jp
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

=end

Actions

Copy link

Updated by mrkn (Kenta Murata) over 13 years ago

Status changed from Open to Closed

=begin
This issue was solved with changeset r29044.
Shumpei, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end

Actions

Copy link

Updated by mrkn (Kenta Murata) over 13 years ago

Category set to core
Status changed from Closed to Assigned
Assignee set to yugui (Yuki Sonoda)

=begin
1.9.2 へのバックポート対象です。

=end

Actions

Copy link

Updated by yugui (Yuki Sonoda) over 13 years ago

Status changed from Assigned to Closed

=begin
This issue was solved with changeset r29370.
Shumpei, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end

Actions

Copy link

Also available in: Atom PDF

Like0

Like0Like0Like0Like0Like0Like0Like0Like0

Project

General

Profile

Ruby » Backport192

Custom queries

Backport #3708

Array#permutation がおかしな結果を返す

Updated by mrkn (Kenta Murata) over 13 years ago

Updated by matz (Yukihiro Matsumoto) over 13 years ago

Updated by mrkn (Kenta Murata) over 13 years ago

Updated by mrkn (Kenta Murata) over 13 years ago

Updated by mrkn (Kenta Murata) over 13 years ago

Updated by mrkn (Kenta Murata) over 13 years ago

Updated by mrkn (Kenta Murata) over 13 years ago

Updated by yugui (Yuki Sonoda) over 13 years ago