Return to Answer

I came out with another solution which would not promise fewer operations, neither less time consumption, but it should be tried to see if it can be a good-enough heuristic to provide less time consumption in huge series of sock pairing.

Preconditions: There is no guarantee that there are the same socks. If they are of the same color it doesn't mean they have the same size or pattern. Socks are randomly shuffled. There can be odd number of socks (some are missing, we don't know how many). Prepare to remember a variable "index" and set it to 0.

The result will have one or two piles: 1. "matched" and 2. "missing"

Heuristic:

1. Find most distinctive sock.
2. Find its match.
3. If there is no match, put it on the "missing" pile.
4. Repeat from 1. until there are no more most distinctive socks.
5. If there are less then 6 socks, go to 11.
6. Pair blindly all socks to its neighbor (do not pack it)
7. Find all matched pairs, pack it and move packed pairs to "matched" pile; If there were no new matches - increment "index" by 1
8. If "index" is greater then 2 (this could be value dependent on sock number because with greater number of socks there are less chance to pair them blindly) go to 11
9. Shuffle the rest
10. Go to 1
11. Forget "index"
12. Pick a sock
13. Find its pair
14. If there is no pair for the sock, move it to the "missing" pile
15. If match found pair it, pack pair and move it to the "matched" pile
16. If there are still more then one socks go to 12
17. If there is just one left go to 14
18. Smile satisfied :)

Also, there could be added check for damaged socks also, as if the removal of those. It could be inserted between 2 and 3, and between 13 and 14.

I have never tried this and am looking forward to hear about any experiences or corrections.

I came out with another solution which would not promise fewer operations, neither less time consumption, but it should be tried to see if it can be a good-enough heuristic to provide less time consumption in huge series of sock pairing.

Preconditions: There is no guarantee that there are the same socks. If they are of the same color it doesn't mean they have the same size or pattern. Socks are randomly shuffled. There can be odd number of socks (some are missing, we don't know how many). Prepare to remember a variable "index" and set it to 0.

The result will have one or two piles: 1. "matched" and 2. "missing"

Heuristic:

1. Find most distinctive sock.
2. Find its match.
3. If there is no match, put it on the "missing" pile.
4. Repeat from 1. until there are no more most distinctive socks.
5. If there are less then 6 socks, go to 11.
6. Pair blindly all socks to its neighbor (do not pack it)
7. Find all matched pairs, pack it and move packed pairs to "matched" pile; If there were no new matches - increment "index" by 1
8. If "index" is greater then 2 (this could be value dependent on sock number because with greater number of socks there are less chance to pair them blindly) go to 11
9. Shuffle the rest
10. Go to 1
11. Forget "index"
12. Pick a sock
13. Find its pair
14. If there is no pair for the sock, move it to the "missing" pile
15. If match found pair it, pack pair and move it to the "matched" pile
16. If there are still more then one socks go to 12
17. If there is just one left go to 14
18. Smile satisfied :)

Also, there could be added check for damaged socks also, as if the removal of those. It could be inserted between 2 and 3, and between 13 and 14.

I'm looking forward to hear about any experiences or corrections.

I came out with another solution which would not promise less operations, neither less time consumption but should be tried to see if it can be good enough heuristic to provide less time consumption in huge series of sock pairing.

Preconditions: There is no guarantee that there are the same socks. If they are of the same color it doesn't mean they have the same size or pattern. Socks are randomly shuffled. There can be odd number of socks(some are missing, we don't know how many). Prepare to remember a variable "index" and set it to 0.

The result will have one or two piles: 1. "matched" and 2. "missing"

Heuristic:

1. Find most distinctive sock.
2. Find its match.
3. If there is no match put it on the "missing" pile.
4. Repeat from 1. until there are no more most distinctive socks.
5. If there are less then 6 socks, go to 11.
6. Pair blindly all socks to its neighbor (do not pack it)
7. Find all matched pairs, pack it and move packed pairs to "matched" pile; If there were no new matches - increment "index" by 1
8. If "index" is greater then 2 ( this could be value dependent on sock number because with greater number of socks there are less chance to pair them blindly  ) go to 11
9. Shuffle the rest
10. Go to 1
11. Forget "index"
12. Pick a sock
13. Find its pair
14. If there is no pair for the sock move it to the "missing" pile
15. If match found pair it, pack pair and move it to the "matched" pile
16. If there are still more then one socks go to 12
17. If there is just one left go to 14
18. Smile satisfied :)

Also, there could be added check for damaged socks also, as if the removal of those. It could be inserted between 2 and 3, and between 13 and 14

I have never tried this and looking forward to hear about any experiences or corrections.

I came out with another solution which would not promise fewer operations, neither less time consumption, but it should be tried to see if it can be a good-enough heuristic to provide less time consumption in huge series of sock pairing.

Preconditions: There is no guarantee that there are the same socks. If they are of the same color it doesn't mean they have the same size or pattern. Socks are randomly shuffled. There can be odd number of socks  (some are missing, we don't know how many). Prepare to remember a variable "index" and set it to 0.

The result will have one or two piles: 1. "matched" and 2. "missing"

Heuristic:

1. Find most distinctive sock.
2. Find its match.
3. If there is no match, put it on the "missing" pile.
4. Repeat from 1. until there are no more most distinctive socks.
5. If there are less then 6 socks, go to 11.
6. Pair blindly all socks to its neighbor (do not pack it)
7. Find all matched pairs, pack it and move packed pairs to "matched" pile; If there were no new matches - increment "index" by 1
8. If "index" is greater then 2 (this could be value dependent on sock number because with greater number of socks there are less chance to pair them blindly) go to 11
9. Shuffle the rest
10. Go to 1
11. Forget "index"
12. Pick a sock
13. Find its pair
14. If there is no pair for the sock, move it to the "missing" pile
15. If match found pair it, pack pair and move it to the "matched" pile
16. If there are still more then one socks go to 12
17. If there is just one left go to 14
18. Smile satisfied :)

Also, there could be added check for damaged socks also, as if the removal of those. It could be inserted between 2 and 3, and between 13 and 14.

I have never tried this and am looking forward to hear about any experiences or corrections.

 1. Find most distinctive sock.
 2. Find its match.
 3. If there is no match put it on the "missing" pile.
 4. Repeat from 1. until there are no more most distinctive socks.
 5. If there are less then 6 socks, go to 11.
 6. Pair blindly all socks to its neighbor (do not pack it)
 7. Find all matched pairs, pack it and move packed pairs to "matched" pile; 
    If there were no new matches - increment "index" by 1
 8. If "index" is greater then 2 ( this could be value dependent on sock 
    number because with greater number of socks there are less chance to 
    pair them blindly ) go to 11
 9. Shuffle the rest 
 10. Go to 1
 11. Forget "index"
 12. Pick a sock
 13. Find its pair
 14. If there is no pair for the sock move it to the "missing" pile
 15. If match found pair it, pack pair and move it to the "matched" pile
 16. If there are still more then one socks go to 12
 17. If there is just one left go to 14
 18. Smile satisfied :)

1. Find most distinctive sock.
2. Find its match.
3. If there is no match put it on the "missing" pile.
4. Repeat from 1. until there are no more most distinctive socks.
5. If there are less then 6 socks, go to 11.
6. Pair blindly all socks to its neighbor (do not pack it)
7. Find all matched pairs, pack it and move packed pairs to "matched" pile; If there were no new matches - increment "index" by 1
8. If "index" is greater then 2 ( this could be value dependent on sock number because with greater number of socks there are less chance to pair them blindly ) go to 11
9. Shuffle the rest
10. Go to 1
11. Forget "index"
12. Pick a sock
13. Find its pair
14. If there is no pair for the sock move it to the "missing" pile
15. If match found pair it, pack pair and move it to the "matched" pile
16. If there are still more then one socks go to 12
17. If there is just one left go to 14
18. Smile satisfied :)