https://bugs.ruby-lang.org/
https://bugs.ruby-lang.org/favicon.ico?1711330511
2010-08-18T18:16:36Z
Ruby Issue Tracking System
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=12871
2010-08-18T18:16:36Z
mrkn (Kenta Murata)
muraken@gmail.com
<ul></ul><p>=begin<br>
むらたです。</p>
<p>On 2010/08/18, at 16:33, Shumpei Akai wrote:</p>
<blockquote>
<p>Array#permutationの結果に,配列に含まれていないはずの値が入っています</p>
<p>% ./ruby_head -e "p [0,1,2,3,4][1,4].permutation.to_a"<br>
[[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]]</p>
<p>[0,1,2,3,4][1,4] は [1, 2, 3, 4] なので0は含まれないはずです.</p>
<p>% ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"<br>
だと正しく動きます</p>
</blockquote>
<p>ary_make_shared 関数を以下のように修正すると正常に動作します。</p>
<p>diff --git a/array.c b/array.c<br>
index 51d3ad2..ea4fe43 100644<br>
--- a/array.c<br>
+++ b/array.c<br>
@@ -409,10 +409,7 @@ static VALUE<br>
ary_make_shared(VALUE ary)<br>
{<br>
assert(!ARY_EMBED_P(ary));</p>
<ul>
<li>if (ARY_SHARED_P(ary)) {</li>
<li>
<pre><code> return ARY_SHARED(ary);
</code></pre>
</li>
<li>}</li>
<li>else if (ARY_SHARED_ROOT_P(ary)) {</li>
</ul>
<ul>
<li>if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {<br>
return ary;<br>
}<br>
else if (OBJ_FROZEN(ary)) {<br>
diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb<br>
index e8edcc2..f2d723f 100644<br>
--- a/test/ruby/test_array.rb<br>
+++ b/test/ruby/test_array.rb<br>
@@ -1549,6 +1549,9 @@ class TestArray < Test::Unit::TestCase<br>
a.permutation {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }<br>
assert_equal(@cls[9, 8, 7, 6], a)<br>
assert_equal(@cls[1, 2, 3, 4].permutation.to_a, b)</li>
<li>
<li>bug3708 = '<a href="https://blade.ruby-lang.org/ruby-dev/42067">[ruby-dev:42067]</a>'</li>
<li>assert_equal(b, @cls[0, 1, 2, 3, 4][1, 4].permutation.to_a, bug3708)<br>
end</li>
</ul>
<pre><code>def test_repeated_permutation
</code></pre>
<p>--<br>
Kenta Murata<br>
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062</p>
<p>本を書きました!!<br>
『Ruby 逆引きレシピ』 <a href="http://www.amazon.co.jp/dp/4798119881/mrkn-22" class="external">http://www.amazon.co.jp/dp/4798119881/mrkn-22</a></p>
<p>E-mail: <a href="mailto:mrkn@mrkn.jp" class="email">mrkn@mrkn.jp</a><br>
twitter: <a href="http://twitter.com/mrkn/" class="external">http://twitter.com/mrkn/</a><br>
blog: <a href="http://d.hatena.ne.jp/mrkn/" class="external">http://d.hatena.ne.jp/mrkn/</a></p>
<p>=end</p>
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=12872
2010-08-18T18:28:59Z
matz (Yukihiro Matsumoto)
matz@ruby.or.jp
<ul></ul><p>=begin<br>
まつもと ゆきひろです</p>
<p>In message "Re: <a href="https://blade.ruby-lang.org/ruby-dev/42068">[ruby-dev:42068]</a> Re: [Bug <a class="issue tracker-4 status-5 priority-4 priority-default closed" title="Backport: Array#permutation がおかしな結果を返す (Closed)" href="https://bugs.ruby-lang.org/issues/3708">#3708</a>] Array#permutation がおかしな結果を返す"<br>
on Wed, 18 Aug 2010 18:16:13 +0900, Kenta Murata <a href="mailto:muraken@gmail.com" class="email">muraken@gmail.com</a> writes:</p>
<p>|On 2010/08/18, at 16:33, Shumpei Akai wrote:<br>
|<br>
|> Array#permutationの結果に,配列に含まれていないはずの値が入っています<br>
|><br>
|> % ./ruby_head -e "p [0,1,2,3,4][1,4].permutation.to_a"<br>
|> [[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]]<br>
|><br>
|><br>
|> [0,1,2,3,4][1,4] は [1, 2, 3, 4] なので0は含まれないはずです.<br>
|><br>
|><br>
|> % ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"<br>
|> だと正しく動きます<br>
|<br>
|<br>
|ary_make_shared 関数を以下のように修正すると正常に動作します。<br>
|<br>
|diff --git a/array.c b/array.c<br>
|index 51d3ad2..ea4fe43 100644<br>
|--- a/array.c<br>
|+++ b/array.c<br>
|@@ -409,10 +409,7 @@ static VALUE<br>
| ary_make_shared(VALUE ary)<br>
| {<br>
| assert(!ARY_EMBED_P(ary));<br>
|- if (ARY_SHARED_P(ary)) {<br>
|- return ARY_SHARED(ary);<br>
|- }<br>
|- else if (ARY_SHARED_ROOT_P(ary)) {<br>
|+ if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {<br>
| return ary;<br>
| }<br>
| else if (OBJ_FROZEN(ary)) {</p>
<p>なるほど。コミットして下さい。</p>
<p>=end</p>
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=12874
2010-08-18T18:47:05Z
mrkn (Kenta Murata)
muraken@gmail.com
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li><li><strong>% Done</strong> changed from <i>0</i> to <i>100</i></li></ul><p>=begin<br>
This issue was solved with changeset r29037.<br>
Shumpei, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<p>=end</p>
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=12875
2010-08-18T19:24:32Z
mrkn (Kenta Murata)
muraken@gmail.com
<ul><li><strong>Status</strong> changed from <i>Closed</i> to <i>Open</i></li></ul><p>=begin<br>
r29037 では SEGV が発生することがあったため、一旦 revert して修正しなおします。</p>
<p>=end</p>
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=12876
2010-08-18T19:36:03Z
mrkn (Kenta Murata)
muraken@gmail.com
<ul></ul><p>=begin<br>
むらたです。</p>
<p>On 2010/08/18, at 18:28, Yukihiro Matsumoto wrote:</p>
<blockquote>
<p>|diff --git a/array.c b/array.c<br>
|index 51d3ad2..ea4fe43 100644<br>
|--- a/array.c<br>
|+++ b/array.c<br>
|@@ -409,10 +409,7 @@ static VALUE<br>
| ary_make_shared(VALUE ary)<br>
| {<br>
| assert(!ARY_EMBED_P(ary));<br>
|- if (ARY_SHARED_P(ary)) {<br>
|- return ARY_SHARED(ary);<br>
|- }<br>
|- else if (ARY_SHARED_ROOT_P(ary)) {<br>
|+ if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {<br>
| return ary;<br>
| }<br>
| else if (OBJ_FROZEN(ary)) {</p>
<p>なるほど。コミットして下さい。</p>
</blockquote>
<p>一旦これでコミットしたのですが、SEGV が発生することがあったため revert しました。</p>
<p>なかださんに ary_make_shared_copy を教えてもらったので、もう一度修正案を提示します。<br>
repeated_permutation、repeated_combination、product も対象です。</p>
<p>diff --git a/array.c b/array.c<br>
index 51d3ad2..bca7956 100644<br>
--- a/array.c<br>
+++ b/array.c<br>
@@ -4010,7 +4010,7 @@ rb_ary_permutation(int argc, VALUE *argv, VALUE ary)<br>
long <em>p = (long</em>)RSTRING_PTR(t0);<br>
volatile VALUE t1 = tmpbuf(n,sizeof(char));<br>
char <em>used = (char</em>)RSTRING_PTR(t1);</p>
<ul>
<li>
<pre><code> VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
</code></pre>
</li>
</ul>
<ul>
<li>
<pre><code> VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
RBASIC(ary0)->klass = 0;
MEMZERO(used, char, n); /* initialize array */
</code></pre>
</li>
</ul>
<p>@@ -4180,7 +4180,7 @@ rb_ary_repeated_permutation(VALUE ary, VALUE num)<br>
else { /* this is the general case */<br>
volatile VALUE t0 = tmpbuf(r, sizeof(long));<br>
long <em>p = (long</em>)RSTRING_PTR(t0);</p>
<ul>
<li>
<pre><code> VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
</code></pre>
</li>
</ul>
<ul>
<li>
<pre><code> 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 */
</code></pre>
</li>
</ul>
<p>@@ -4266,7 +4266,7 @@ rb_ary_repeated_combination(VALUE ary, VALUE num)<br>
else {<br>
volatile VALUE t0 = tmpbuf(n, sizeof(long));<br>
long <em>p = (long</em>)RSTRING_PTR(t0);</p>
<ul>
<li>
<pre><code> VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
</code></pre>
</li>
</ul>
<ul>
<li>
<pre><code> 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 */
</code></pre>
</li>
</ul>
<p>@@ -4325,7 +4325,7 @@ rb_ary_product(int argc, VALUE <em>argv, VALUE ary)<br>
/</em> Make defensive copies of arrays; exit if any is empty */<br>
for (i = 0; i < n; i++) {<br>
if (RARRAY_LEN(arrays[i]) == 0) goto done;</p>
<ul>
<li>
<pre><code> arrays[i] = ary_make_substitution(arrays[i]);
</code></pre>
</li>
</ul>
<ul>
<li>
<pre><code> arrays[i] = ary_make_shared_copy(arrays[i]);
}
</code></pre>
}<br>
else {<br>
--- a/test/ruby/test_array.rb<br>
+++ b/test/ruby/test_array.rb<br>
@@ -1528,6 +1528,10 @@ class TestArray < Test::Unit::TestCase<br>
acc = [1,2].product(*[o]*10)<br>
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]),<br>
acc)</li>
<li>
<li>a = []</li>
<li>[1, 2].product([0, 1, 2, 3, 4][1, 4]) {|x| a << x }</li>
<li>assert(a.all?{|x| !x.include?(0) })<br>
end</li>
</ul>
<pre><code>def test_permutation
</code></pre>
<p>@@ -1574,6 +1578,9 @@ class TestArray < Test::Unit::TestCase<br>
a.repeated_permutation(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }<br>
assert_equal(@cls[9, 8, 7, 6], a)<br>
assert_equal(@cls[1, 2, 3, 4].repeated_permutation(4).to_a, b)<br>
+</p>
<ul>
<li>a = @cls[0, 1, 2, 3, 4][1, 4].repeated_permutation(2)</li>
<li>assert(a.all?{|x| !x.include?(0) })<br>
end</li>
</ul>
<pre><code>def test_repeated_combination
</code></pre>
<p>@@ -1600,6 +1607,9 @@ class TestArray < Test::Unit::TestCase<br>
a.repeated_combination(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }<br>
assert_equal(@cls[9, 8, 7, 6], a)<br>
assert_equal(@cls[1, 2, 3, 4].repeated_combination(4).to_a, b)<br>
+</p>
<ul>
<li>a = @cls[0, 1, 2, 3, 4][1, 4].repeated_combination(2)</li>
<li>assert(a.all?{|x| !x.include?(0) })<br>
end</li>
</ul>
<pre><code>def test_take
</code></pre>
<p>--<br>
Kenta Murata<br>
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062</p>
<p>本を書きました!!<br>
『Ruby 逆引きレシピ』 <a href="http://www.amazon.co.jp/dp/4798119881/mrkn-22" class="external">http://www.amazon.co.jp/dp/4798119881/mrkn-22</a></p>
<p>E-mail: <a href="mailto:mrkn@mrkn.jp" class="email">mrkn@mrkn.jp</a><br>
twitter: <a href="http://twitter.com/mrkn/" class="external">http://twitter.com/mrkn/</a><br>
blog: <a href="http://d.hatena.ne.jp/mrkn/" class="external">http://d.hatena.ne.jp/mrkn/</a></p>
<p>=end</p>
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=12887
2010-08-19T12:17:05Z
mrkn (Kenta Murata)
muraken@gmail.com
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li></ul><p>=begin<br>
This issue was solved with changeset r29044.<br>
Shumpei, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<p>=end</p>
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=12888
2010-08-19T12:45:07Z
mrkn (Kenta Murata)
muraken@gmail.com
<ul><li><strong>Category</strong> set to <i>core</i></li><li><strong>Status</strong> changed from <i>Closed</i> to <i>Assigned</i></li><li><strong>Assignee</strong> set to <i>yugui (Yuki Sonoda)</i></li></ul><p>=begin<br>
1.9.2 へのバックポート対象です。</p>
<p>=end</p>
Backport192 - Backport #3708: Array#permutation がおかしな結果を返す
https://bugs.ruby-lang.org/issues/3708?journal_id=13591
2010-09-29T21:27:06Z
yugui (Yuki Sonoda)
yugui@yugui.jp
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li></ul><p>=begin<br>
This issue was solved with changeset r29370.<br>
Shumpei, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<p>=end</p>