Re: Re: Shortest string containing all from 0000 to 9999 challenge.

A better lower bound is 10! Every permutation of the 10 digits will change a valid solution to another valid solution.

~~Wrong~~.

By the way it's not that sure that you can start with every 4 digit number. I think you can - but you need to prove it.

Update: Or is it right? Let's have two differend 4 digit strings - if they are different then at least on one of the 4 position they have different digits - the permutation will change those digits to different digits as well. It means the permutation induces a 1-1 function on the 10000 4 digit strings. There can't be any more of them so in the whole resulting string there will be exactly 10000 different 4 digit strings. QED

That was long time since I proved a theorem.

Comment on Re: Re: Shortest string containing all from 0000 to 9999 challenge.

Replies are listed 'Best First'.
Re: Re: Re: Shortest string containing all from 0000 to 9999 challenge. by sauoq (Abbot) on May 22, 2003 at 20:12 UTC
By the way it's not that sure that you can start with every 4 digit number. I think you can - but you need to prove it. You can. First, it is sufficient to prove that you can do it with every possible pattern of same/differing numbers. Permutations take care of the rest. (Your thinking on that was fine, by the way.) There are only twelve such patterns: `AAAA AAAB AABA ABAA BAAA AABC ABAC ABCA BAAC BACA BCAA ABCD`. All you have to do is choose A, B, C, and D as four different digits and find a solution for each one. I chose A=0, B=1, C=2, and D=3 and then, using the same code in my original solution, found that there was indeed a solution for each of the 12 patterns. So, for a lower bound, we have at least 12 * 10! (or the number of starting patterns multiplied by the permutations.) Some other interesting facts (proofs left as an exercise): The reverse of a valid solution is a valid solution. No valid solutions are palindromic. -sauoq "My two cents aren't worth a dime.";	[reply]
Re: Re: Re: Shortest string containing all from 0000 to 9999 challenge. by BrowserUk (Patriarch) on May 22, 2003 at 11:36 UTC
I meant unique in the 'these two string compare differently' sense, rather that the set theory sense. Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller	[reply]