Bug #21449: Set#divide is order dependent and not working correctly

• Status: Closed
• Assignee: -
• Target version: -
• ruby -v: ruby 3.5.0dev (2025-06-23T11:03:48Z master af6b98f7a2) +YJIT +MN +PRISM [arm64-darwin22]
• Backport: 3.2: UNKNOWN, 3.3: UNKNOWN, 3.4: UNKNOWN

[tompng (tomoya ishida)]

Set[0,1,2,3].divide{(_1 - _2).abs == 1}
#=> #<Set: {#<Set: {0, 1, 2, 3}>}>

Set[0,2,3,1].divide{(_1 - _2).abs == 1}
#=> #<Set: {#<Set: {0, 1, 2, 3}>}> (ruby 3.4)
#=> #<Set: {#<Set: {0, 1}>, #<Set: {2, 3, 1}>}> (ruby 3.5.0dev)

Result of Set#divide wrongly depends on set order.

Set.new(1000.times.to_a.shuffle).divide{(_1 - _2).abs == 1}.size
#=> 1 (ruby 3.4)
#=> 250±20 (ruby 3.5.0dev)

[tompng (tomoya ishida)]

pull request https://github.com/ruby/ruby/pull/13680

[tompng (tomoya ishida)]

• Status changed from Open to Closed

Applied in changeset git|67346a7d94b101acc00c177b01ad0aabfef605a8.

---

[Bug #21449] Fix Set#divide{|a,b|} using Union-find structure (#13680)

• [Bug #21449] Fix Set#divide{|a,b|} using Union-find structure

Implements Union-find structure with path compression.
Since divide{|a,b|} calls the given block n**2 times in the worst case, there is no need to implement union-by-rank or union-by-size optimization.

• Avoid internal arrays from being modified from block passed to Set#divide

Internal arrays can be modified from yielded block through ObjectSpace.
Freeze readonly array, use ALLOCV_N instead of mutable array.