Question

there is a 4 digit number, using the digits through 0,1,2,3,4...9
What is one of the lowest number of digits that would cover all the possible combinations?

For example: If you had a 2 digit number using only digits 0,1 then
00110, is a number that cover all the possibilites 00,01,11,10

Answer 1

@ganeshie8 @ikram002p

Answer 2

Well if it's a 4 digit number, wouldn't you be missing out on the combinations formed by other 5 digits

Answer 3

interesting... so you want to cover all the 4 digit numbers in a number

Answer 4

i was thinking of the process for concatenating when it comes to the 2 digit stage
00,01,10,11

lets say you pick
lets say u pick 01,now u wud see a number starting with 1 on the list that is not picked so 11 so you have 011 now you see another number u have no picked starting with a 1,that would be 10 so 0110 now you see another number starting with 0 you have not picked thats 00, so u have 01100, and now u have picked all the numbers

Answer 5

but this seems like a very computery solution, there has to be a more logical approach

Answer 6

lets see if we can find a pattern with 2 digits, that makes use of digits 0 to 9
so there are
100 permutations in total that you want to hit with the smallest number possible

Answer 7

it has to start with `001`...

Answer 8

it can start anyway

Answer 9

you want the smallest right

Answer 10

yeah

Answer 11

for example in the 2 digit , and numbers 0,1 only case u have
00110
11001
01101
10011
4 different cases

Answer 12

you want to cover all possible 4 digit combinations using the smallest number possible?

Answer 13

theres more than that too

Answer 14

oh i see sorry for the confusion, i meant hte shortest path smallest number of digits

Answer 15

Have you heard of Goulomb rulers or Costas Arrays?

Answer 16

well anyways the number of 4 digit number you can get is..
\[10\times 9 \times 8 \times 7 =5040\]

Answer 17

that's a lot of combinations

Answer 18

i think i remember u posting a link about some ruler, i did not get a chance to look thru it though

Answer 19

10,000 combinations, 40,000 digits 10^4 combinations

Answer 20

http://datagenetics.com/blog/february22013/index.html

It might or might not help you, it seems related though.

Answer 21

oh so you want the digits to repeat too

Answer 22

in that case 10^4=10,000 combinations, yep..

Answer 23

for covering permutations of 2 digits we can find a number with digits <= 2*10^2

Answer 24

hey here is an idea

Answer 25

kind of like a graph theory solution

Answer 26

Yeah this is quite interesting. To help give myself a little insight while playing around with a finite example I'm using 0,1,2 and looking at all 3^3 combinations we can make and then restricting it to arbitrary numbers and looking for overlaps in the patterns to try to see what there is.

Honestly it seems as though the digits we choose might not even matter since there will always be some overlap at 4 digits. For this I mean go back to the original example with ones and zeroes we could have any of these as answers:

00110
01100
11001
10011

So there are 2^2 possible answers with 2^2 possible configurations. Not a coincidence I think.

Answer 27

for example if u look at
00,01,10,11
there four digits, there are multiple ways to jump from one number, in such a way that the last digit and the first digiht of our numbers correspond

Answer 28

if we graph all the possible paths lest say is there a certain way to find shortest paths taht pass thru them all

Answer 29

Look at what I wrote, it looks like group theory, we're shifting all the numbers to the left in a cycle haha.

Answer 30

oh true yeah

Answer 31

this reminds me of grey code in k-maps

Answer 32

lets look at the process wed go for just picking 1 instance of the number that can be shifted though

Answer 33

Actually if you look at what I wrote it is sort of like we took the repeating string:

11001100110011001100...

and then we just took out a 5 character substring and slid our little viewer down the line

Answer 34

yeah

Answer 35

Maybe that means we can always include what we are looking for in a section that's n^n+1

Answer 36

or n^n+n-1, we don't really have enough information to say yet

Answer 37

(just making stuff up tbh)

Answer 38

n^n+1 is actually right

Answer 39

So you can contain all 3 digits 0,1, and 2 in every possible permutation in a string only 28 digits long?

Answer 40

yep

Answer 41

Ohhh how do you know that? HAhahahah well that was a lucky guess, thank you math gods.

Answer 42

lol

Answer 43

i tried writing out 3 digits

Answer 44

theres an easy programming solution but its not that efficient to find the shortest path

Answer 45

you imagine then numbers in a circle

Answer 46

and you input numbers in between so u are always checking with both ends to see u arent making something that already exists

Answer 47

for the actual problem the string length is 10^4+1 ?

Answer 48

yeah

Answer 49

grey code string length is also 10^4+1 so i think grey code will do the job here

Answer 50

wuts that

Answer 51

Oh so what I wrote is similar except instead of it being a circle it's just a periodic sequence, so I think I'm actually doing the same thing slightly differently

Answer 52

order the four digit numbers such that only one position changes between the transitions

Answer 53

a grey code order for decimal four digit numbers could be :

1248, 1249, 1259, 1269, 1279, 1289, 1299, 1399, ...

Answer 54

we can work our minimum string like this :

0000
0001
0010
0100
1000
0002
0020
0200
....

Answer 55

`00001000200...`

Answer 56

yeah but changing it such that only 1 change doesnt always gurantee smallest solution , how do u pick the right one change for example
00,01,10,01,11 <--- this is a bad path to take for only 1 change
00,01,11,10 ---> this is the right path to take

Answer 57

oh i see 2 changes happened for that one

Answer 58

okay i see what u mean!!

Answer 59

I found this really nice picture of Gray codes and it shows not only that each code is only different by one bit from one to the next but it also shows how they are periodic at each layer, interesting http://admin.morkalork.com/uploads/images/binaries/BinaryCircelGray2.png

Answer 60

11,10,00,01
11001 wow it works : )

Answer 61

what the method u showed above, do the digits have to flow in that order and why?

Answer 62

for the minimum number they need to follow that order
if we just want a random 10^4+1 digit string, you can work the gray code in any way we wish

Answer 63

its not working like theres different cases where it fails

Answer 64

changing bits ranomly 1 bit at a time i mean, i dont know if having in a paritcular older like grey code fixes it

Answer 65

after `1234`, below are few possible next terms in gray code sequence :

2234
1334
1244
1235

Answer 66

just stick to a particular pattern from the start and work it.. you will get back to the starting number after permuting everything..

Answer 67

0000 ----- 10^4-1 terms ---- 0000

Answer 68

lets look at 3 bit gray code counter in binary :

000 --> 001 --> 011 --> 010 --> 110 --> 111 --> 101 --> 100 --> 000

Answer 69

http://prntscr.com/65sjvu

Answer 70

No thats not a mistake.. gray code only guarantees that you can count the four digit permutations by changing one bit at a time

Answer 71

Idk if its possible for array of nine different digits like for the binary u gave it was possible hmm we have different possibilities :/

Answer 72

hey i found like some part of the pattern that is unavoidable

Answer 73

Show them plz

Answer 74

like lets say its starting at 0, for a 3 digit code, that uses 0,1,2
001002011012022... this way of counting this part must exist in all the solutions

Answer 75

I think you can arrange it better to get the smallest

Answer 76

yeah gray code as it is wont work
you're saying something about arranging numbers in a circle ?

Answer 77

Circle would be interesting though

Answer 78

So instead of array make Que

Answer 79

uhh i saw the solution its not simple at all xD, there is a very efficient computer algorithm for it

Answer 80

i realize that haha.. can i see the solution xD

Answer 81

https://www.youtube.com/watch?v=iPLQgXUiU14

Answer 82

Since there are multiple ways to create the best sequence for breaking a lock, is there some way we can take it a step further and weigh it so the more common locks people would make such as 1111 or 1212 would appear first rather than something obscure like 2619 or something? Or just some general way of weighting it?

Answer 83

well wed have to give up on the size of the numbers then otherwise, start at a better place in that sequence

Answer 84

this does pose some more interesting questions though like

Answer 85

what is the shortest path considering weights

Answer 86

what is the least weighted path

Answer 87

it sounds extremely complicated though, this looks like something hacking algorithms would be like

Answer 88

actually hmm, were u the one that made me watch that guy who was presenting on most common passwords

Answer 89

Yeah haha

Answer 90

lol

Answer 91

well lets suppose we had a way to just reorder all the 4 digit code in order according to weight

Answer 92

and try to think of like an algorithm on how to sequence based on, a couple things like? the weight of the numbers you are sequencing , the number of heavy weights u are eliminating with certain sequencing

Answer 93

feel like its a solution only computers can be working on but even then trying to find an efficient way of going about it would be really interseting

Answer 94

Well we already know we have to arrange it in n^n+1 digits and that there are... n^n different ways of doing it?

Answer 95

oh okay u wanna see like the best path for thhe already shortest pathh

Answer 96

thats pretty simple i feel

Answer 97

just weight them all and run a count on weight