The search functionality is under construction.

Keyword Search Result

[Keyword] mathematical puzzles(1hit)

1-1hit
  • Efficient Algorithms for Sorting k-Sets in Bins

    Atsuki NAGAO  Kazuhisa SETO  Junichi TERUYAMA  

     
    PAPER-Fundamentals of Information Systems

      Vol:
    E98-D No:10
      Page(s):
    1736-1743

    We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $ rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $ rac{15}{16}n^2+O(n)$ swaps for k=3.