8 Replies - 939 Views - Last Post: 18 September 2011 - 09:27 AM

#1 novacrazy  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • Posts: 117
  • Joined: 01-March 11

Sequence composition algorithm

Posted 17 September 2011 - 07:56 PM

I've been looking for stuff on this for a while now, but I can't seem to find anything. All I'm asking is for a link to some wiki page or something for a possible solution.

Say I have the sequence 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.
Since the sums of any of them are not equal to the sums of any others, I've been using them for a variety of error codes in my programs, however, figuring up what the sums are made of has proven a little difficult.

So, I'm looking for a way to say, for example, that 1153 = 128 + 1024. Or more complex ones like 8800 = 16 + 32 + 128 + 512 + 8192.

I've honestly no idea where to start with this, and I've looked up stuff about various geometric sequences, but they don't mention figuring out this sort of thing. Any ideas would be greatly appreciated :)

Is This A Good Question/Topic? 0
  • +

Replies To: Sequence composition algorithm

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10667
  • View blog
  • Posts: 39,615
  • Joined: 27-December 08

Re: Sequence composition algorithm

Posted 17 September 2011 - 08:02 PM

I would start by generating the sequence of terms <= the number n. While n > 0, subtract the largest element in the sequence from n, so long as that number does not exceed n.
Was This Post Helpful? 0
  • +
  • -

#3 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Sequence composition algorithm

Posted 17 September 2011 - 08:24 PM

I'd go with dynamic programming on this one. If you know know how to calculate the sequence up to n. Then apply the subset sum algorithm. Ofcourse you may wanna generate the sequence in advance up to a sufficient number to avoid having to generate it for each in.
Was This Post Helpful? 0
  • +
  • -

#4 tlhIn`toq  Icon User is offline

  • Please show what you have already tried when asking a question.
  • member icon

Reputation: 5582
  • View blog
  • Posts: 11,941
  • Joined: 02-June 10

Re: Sequence composition algorithm

Posted 18 September 2011 - 07:19 AM

This is just bitwise comparrison and we do it a lot for flags and enumerations.


Enum Modes
{
   UNKNOWN = 0,
   CLERK   = 1,
   MANAGER = 2,
   SUPERVISOR = 4,
   OWNER   = 8
}

Modes myMode = Modes.MANAGER; // Thus equal to 2

bool IsManager()
{
   if ((myModes & MODES.Manager) == (MODES.Manager)) return true;
   return false; // Only reaches this line if not true
}

Was This Post Helpful? 0
  • +
  • -

#5 RetardedGenius  Icon User is offline

  • >>──(Knee)──►
  • member icon

Reputation: 126
  • View blog
  • Posts: 555
  • Joined: 30-October 10

Re: Sequence composition algorithm

Posted 18 September 2011 - 08:38 AM

I hate to be the newb here, but if someone could kindly explain what you're all 'on about' I'd be greatly appreciative! :D
Was This Post Helpful? 0
  • +
  • -

#6 novacrazy  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • Posts: 117
  • Joined: 01-March 11

Re: Sequence composition algorithm

Posted 18 September 2011 - 08:59 AM

I'd have to agree with macosxnerd101 and mostyfriedman. I'll post what I end up with when I get around to making it.

And to tlhIn`toq, yeah, that's how you'd normally do something like that... However, I'm using a system similar to errno, and one that I decided could hold multiple values at a time for the fun of it, for if multiple things happen in one function, etc(not the best reasons to do so, but it makes things interesting and fun). So preset comparisons or even a small lookup table would be a little less 'clean and beautiful' than I'd like.

To RetardedGenius, Imma just trying to figure out that given the sequence I listed above, how could you figure out that a number such as 1152 is made up of 128 and 1024. Something like that, for any value that is a sum of any of those numbers.
Was This Post Helpful? 0
  • +
  • -

#7 tlhIn`toq  Icon User is offline

  • Please show what you have already tried when asking a question.
  • member icon

Reputation: 5582
  • View blog
  • Posts: 11,941
  • Joined: 02-June 10

Re: Sequence composition algorithm

Posted 18 September 2011 - 09:11 AM

View Postnovacrazy, on 18 September 2011 - 09:59 AM, said:

And to tlhIn`toq, yeah, that's how you'd normally do something like that... However, I'm using a system similar to errno, and one that I decided could hold multiple values at a time for the fun of it, for if multiple things happen in one function, etc


I have no idea what 'errno' is.
Just to be sure you realize, but you can hold multiple values with flags. That's sort of the point. YOu just 'or' them together with |


myModes = Modes.CLERK | Modes.OWNER;


Then when you need to know if they have permissions as a Clerk or an Owner you check.

if (IsClerk || IsOwner) console.WriteLine("You have permission");

bool IsClerk()
{
   if ((myModes & Modes.CLERK) == (Modes.CLERK)) return true;
   return false; // Only reaches this line if not true
}
bool IsOwner()
{
   if ((myModes & Modes.OWNER) == (Modes.OWNER)) return true;
   return false; // Only reaches this line if not true
}



I do things like this all the time for logging.

Enum LogEvents
{
   UNKNOWN = 0,
   DRIVES = 1,
   PORTS = 2,
   VIDEO = 4,
   CAMERA = 8,
   // 16,
   // 32,
   // 64
   // 128
   VERBOSE = 256
}


Then set the event catagories I'd like to log with:

LogEvents LogTheseThings = LogEvents.DRIVES | LogEvents.VIDEO;


Usually set by a series of checkboxes on a preferences control.
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10667
  • View blog
  • Posts: 39,615
  • Joined: 27-December 08

Re: Sequence composition algorithm

Posted 18 September 2011 - 09:18 AM

I think this is a math modeling problem, not an instance of checking permissions. I can't imagine the sequence for 2^n would be great for flags. :P
Was This Post Helpful? 0
  • +
  • -

#9 novacrazy  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • Posts: 117
  • Joined: 01-March 11

Re: Sequence composition algorithm

Posted 18 September 2011 - 09:27 AM

View Postmacosxnerd101, on 18 September 2011 - 10:18 AM, said:

I think this is a math modeling problem, not an instance of checking permissions. I can't imagine the sequence for 2^n would be great for flags. :P

It's kind of both :P No, it's not that great for flags and such, but I'm finding it fun to try to use it like that. Though this particular question was mostly for the math.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1