0

I've got a route that contains objects. Each one has value 0 or 1. I need unique route ID which will identify any objects order. Currently I'm doing it using binary number that is converted to decimal (see picture).

Objects

The problem is, that amount of objects in route is up to 15. So, decimal number will be very big (up to 32767) with many values, that will never be used.
How to convert that number, to another unique value, but much smaller (<255)? I need to do that, only by using simple arithmetical operators (+,-,*,div).

Djent
  • 101
  • 1
  • did you consider [hashing](http://programmers.stackexchange.com/a/145633/31260)? [Sharing your research helps everyone](http://meta.programmers.stackexchange.com/questions/6559/why-is-research-important). Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see [ask] – gnat May 08 '14 at 07:40
  • 1
    "Each one has value 0 or 1" and "with many values, that will never be used" are in contradiction - if *each* value *can* be 0 or 1, then there are 2^15 routes... – AakashM May 08 '14 at 08:11
  • 1
    OK, now I see it - it's really imposible to make that number smaller. Thank you. – Djent May 08 '14 at 08:20
  • Unless you only want the unique id within a predefined subset? eg for 0000011000000000 0000111000000000 and 0000010000000000 unique would be 011 111 and 010. This would not hold however if the collection is mutable. – Me.Name May 08 '14 at 08:30
  • I don't get it, the resulting binary number itself is a unique id in the sequence, isn't it? Alternatively, you can represent the number in a non-base10 system, for example hex (or even make up your own) . – jordan May 08 '14 at 11:15

3 Answers3

3

You have the equivalent of 15 bits of information that you must save. The largest binary number represented by 15 bits is 32767, and it is by no means no coincidence that this is also the maximum number of possible combinations (-1).

You cannot reduce this number without first providing some sort of simplification rule (i.e. the number must be an odd number, the number must be a palindrome, etc.). Otherwise any combination of the 15 bits is allowed.

While you may perform mathematical operations to simplify this number just the same, you'd be losing information in the process, and hence it would be one-directional (you could not figure out the original number by reversing the mathematical operation(s)).

Neil
  • 22,670
  • 45
  • 76
  • I don't need to reverse combination. Any order can occur. It can contain 3 objects or 15. I need to assign unique ID for any route. – Djent May 08 '14 at 08:15
  • @Djent Then using 1 for a selected object and 0 for an unselected object in a binary number is as good as any for representing it. – Neil May 08 '14 at 08:20
2

Assumed, you will travel only a certain subset of all possible routes ever.

In that case, you could use a mapping between the routebits and a incremented numerical id. You will have to store that mapping somewhere, but this way every path used gets an unique id assigned, which can be used to refer to it later.

I'm not so sure if this is an efficient way to do it, but you didn't ask for that aspect.

JensG
  • 2,423
  • 1
  • 19
  • 25
1

It's impossible because each route may be reached (or not?). You have as many routes as 2^15

Maybe You have to consider fact that some of them will never appears (is it true?). So You can number only this of them which can be reached. This will decrease Your number of ways.

To decrease number of routes to be from 0 to 255 You have to eliminate about 2^7 routes. This may mean that seven objects will have always the same value (0 or 1).

For example

  • ffff1101fff10111
  • ffff0101fff00101
  • ffff0111fff10100

etc...

Andrzej Reduta
  • 111
  • 4