Date: 12/22/05     Keywords: web

Hello,

I ran into a combinatorics problem in a website I'm developing. I can't for the life of me figure this one out... I'd be very grateful if anyone could help me with this.

You're given n lists of elements, where an element consists of a unique identifier and a number. These lists are of various lengths and are all sorted from low to high based on the element's number. You want to generate all sequences of elements, where each sequence contains exactly one element from every list. The catch is that you need to generate these sequences in sorted order. The sort value for a sequence is simply the sum of all numbers from the elements in that sequence.

For example if you had just two lists:

List 1: {A-10, B-20}
List 2: {D-1, E-2, F-100}

You would return the following order of sequences:
{A,D}, {A,E}, {B,D}, {B,E}, {A,F}, {B,F}
as that would give you the sort values:
11, 12, 21, 22, 110, 120

I can't just calculate all combinations and then sort them, as my application would typically have billions of combinations and I only need the top 100. I need to do this in sorted order.

Thanks for the help!

Source: http://community.livejournal.com/algorithms/68721.html

Date: 12/17/05     Keywords: no keywords

Let me start off by saying I don't know much too in details about frequencies assignements in cell phones. However I am working on a project that cell phone frequencies can be one of the applications that might take advantage of it. So here's the question:

I believe that a cell requires a single frequency is popular (and also easiest) however could there be a situation that the cell phone requires "X" assigned frequencies where "X" is larger than or equal to total number of cell phones available in that network ?

Note that I am talking about a general, real world mobile network, Verizon etc ... Also if this is not the appropriate community for this question, do you know of any other ?


Oh yeh, can I do cross-posting if I want to ask the same question to multi communities ? If so, how does that work in LJ ?

Thanks !


note I understand they can share frequencies but could there be a case that the number of distinct frequencies assigned to a cell phone be ever larger or equal to the number of cell phones available, in general mobile network ?

Let's say Verizon has 1 million cell phones in its network , can there be >= 1 million frequencies assigned to cell phone ? Is there any document, technical paper that I can reference to that state this ?



I am just trying to tie this problem with the algorithm I am working on which is called Multi coloring , that is on a graph (containing vertices and edges), each vertices has a number of colors (that are not the same to any other), the problem is to use as little colors as possible and assigned to these vertices such that the there are no collision in colors (e.g., colors of a vertex cannot be the same, and colors of vertex v1 cannot be the same as colors of vertex v2 if v1 connects to v2 or vice versa). It has been said that the channel frequency problem in cell phone can be similar to this, cell -> vertex, channel frequencies -> number of colors a vertex can have ...


I just found this article http://electronics.howstuffworks.com/cell-phone1.htm , it says cell phone can works at 1600 something frequencies, which basically is nothing comparing to the number of cell phones in a network. Does it sound right ?


Is there any rule about putting a post in MY journal, and just refer the links to the communities ? Because cross-posting and managing answers are confusing :)

Source: http://www.livejournal.com/community/algorithms/68567.html

Date: 12/17/05     Keywords: no keywords

Let me start off by saying I don't know much too in details about frequencies assignements in cell phones. However I am working on a project that cell phone frequencies can be one of the applications that might take advantage of it. So here's the question:

I believe that a cell requires a single frequency is popular (and also easiest) however could there be a situation that the cell phone requires "X" assigned frequencies where "X" is larger than or equal to total number of cell phones available in that network ?

Note that I am talking about a general, real world mobile network, Verizon etc ... Also if this is not the appropriate community for this question, do you know of any other ?


Oh yeh, can I do cross-posting if I want to ask the same question to multi communities ? If so, how does that work in LJ ?

Thanks !


note I understand they can share frequencies but could there be a case that the number of distinct frequencies assigned to a cell phone be ever larger or equal to the number of cell phones available, in general mobile network ?

Let's say Verizon has 1 million cell phones in its network , can there be >= 1 million frequencies assigned to cell phone ? Is there any document, technical paper that I can reference to that state this ?



I am just trying to tie this problem with the algorithm I am working on which is called Multi coloring , that is on a graph (containing vertices and edges), each vertices has a number of colors (that are not the same to any other), the problem is to use as little colors as possible and assigned to these vertices such that the there are no collision in colors (e.g., colors of a vertex cannot be the same, and colors of vertex v1 cannot be the same as colors of vertex v2 if v1 connects to v2 or vice versa). It has been said that the channel frequency problem in cell phone can be similar to this, cell -> vertex, channel frequencies -> number of colors a vertex can have ...


I just found this article http://electronics.howstuffworks.com/cell-phone1.htm , it says cell phone can works at 1600 something frequencies, which basically is nothing comparing to the number of cell phones in a network. Does it sound right ?


Is there any rule about putting a post in MY journal, and just refer the links to the communities ? Because cross-posting and managing answers are confusing :)

Source: http://community.livejournal.com/algorithms/68567.html

Date: 12/10/05     Keywords: web

You might remember a few weeks ago someone posted about a clique* finder for LJ. I wrote another program to do this, using an algorithm that finds exact solutions. It runs quite fast for inputs up to around 200 or so (it takes < 1 second for anything up to around 140). Also, it finds all cliques, not just the maximal one.

I tried it against the clique finder that was linked in that discussion, and the results seem to match, though I only tried a few usernames.

I don't have a nifty web interface set up for it (it's in Perl, with the clique-finding code in C++), and I wouldn't have anywhere to host it if I did, but if you are interested I can run some queries on it.

* My definition of a clique is a group where every pair of members are MUTUAL friends, and no member can be added to the group while maintaining this property.

Source: http://www.livejournal.com/community/algorithms/68226.html

Date: 12/10/05     Keywords: web

You might remember a few weeks ago someone posted about a clique* finder for LJ. I wrote another program to do this, using an algorithm that finds exact solutions. It runs quite fast for inputs up to around 200 or so (it takes < 1 second for anything up to around 140). Also, it finds all cliques, not just the maximal one.

I tried it against the clique finder that was linked in that discussion, and the results seem to match, though I only tried a few usernames.

I don't have a nifty web interface set up for it (it's in Perl, with the clique-finding code in C++), and I wouldn't have anywhere to host it if I did, but if you are interested I can run some queries on it.

* My definition of a clique is a group where every pair of members are MUTUAL friends, and no member can be added to the group while maintaining this property.

Source: http://community.livejournal.com/algorithms/68226.html

Date: 12/01/05     Keywords: no keywords

One of the most frustrations in my current project is it takes a long time in order to see if the modification creates any difference. Since heuristic randomness is involved, I need to take the average answer (e.g., trial -> running the program for 100 times / get the best & average). Each trial can take a longggggggggg period of time.

It's also frustrated that it's difficult to know what values, combination, settings etc would be good to use or to avoid.


What do you do in such case ?

Source: http://www.livejournal.com/community/algorithms/67896.html

Date: 12/01/05     Keywords: no keywords

One of the most frustrations in my current project is it takes a long time in order to see if the modification creates any difference. Since heuristic randomness is involved, I need to take the average answer (e.g., trial -> running the program for 100 times / get the best & average). Each trial can take a longggggggggg period of time.

It's also frustrated that it's difficult to know what values, combination, settings etc would be good to use or to avoid.


What do you do in such case ?

Source: http://community.livejournal.com/algorithms/67896.html

Date: 12/01/05     Keywords: no keywords

Hello, I'm new to this community (mostly due to not looking into communities on LJ), and have a quick question.

How would the fastest algorithm to tackle the N-Queens problem be written? I currently have a depth-first search written in C++, but this runs too slow for higher values of N. Also, could someone provide hints or help on how to incorporate symmetry into the program? Any help would be greatly appreciated, thanks.

Source: http://www.livejournal.com/community/algorithms/67606.html

Date: 12/01/05     Keywords: no keywords

Hello, I'm new to this community (mostly due to not looking into communities on LJ), and have a quick question.

How would the fastest algorithm to tackle the N-Queens problem be written? I currently have a depth-first search written in C++, but this runs too slow for higher values of N. Also, could someone provide hints or help on how to incorporate symmetry into the program? Any help would be greatly appreciated, thanks.

Source: http://community.livejournal.com/algorithms/67606.html

Date: 11/30/05     Keywords: php, database, shopping

So every year my friends and I do a Secret Santa exchange (the basic idea under a normal setup is to take a set of n names and derange them, so each person buys a gift for someone else, the 'secret' part being that nobody knows who's shopping for whom)... but we have a large group and there's some people who simply don't know each other, so being the programmer that I am, I scripted up a few PHP pages and a database to allow people to sign up to partipate, and then select the members that they would be willing to shop for. Ideally, I can call the "assignment" algorithm, write the results back to the database, and never know who has whom.

The trick now is to write an efficient (ideally! correctness is vital, no approximations! and n is not THAT large that exponential is out of the question) algorithm to find the shopping assignments OR prove that the input does not allow an assignment where every participant is: 1) being shopped for by exactly one person and 2) shops for exactly one person other than himself

Algorithmically speaking:

GIVEN:
D, a simple digraph (no loops), where a node is a person and an edge from X to Y indicates X is willing to shop for Y

FIND:
D', a subset of D, where forall v in V, indegree(v) = outdegree(v) = 1. D' need not be connected (there is no guarantee D is). OR prove that given D, there is no satisfying D'.

CONSTRAINTS:
Must be correct. Time is key. A large but reasonable amount of space may be used. Bonus points if the algorithm can be randomized (or even produces different output if you start at a different node, so long as other constraints are still met).


Since I have a small n, I can play around with insane solutions like "select a random assignment, check for validity, if not valid repeat"... but it seems like there should be some sort of algorithm to do this, but at the same time, I wonder if maybe it is more difficult than it seems...

Source: http://www.livejournal.com/community/algorithms/67335.html

Date: 11/30/05     Keywords: php, database, shopping

So every year my friends and I do a Secret Santa exchange (the basic idea under a normal setup is to take a set of n names and derange them, so each person buys a gift for someone else, the 'secret' part being that nobody knows who's shopping for whom)... but we have a large group and there's some people who simply don't know each other, so being the programmer that I am, I scripted up a few PHP pages and a database to allow people to sign up to partipate, and then select the members that they would be willing to shop for. Ideally, I can call the "assignment" algorithm, write the results back to the database, and never know who has whom.

The trick now is to write an efficient (ideally! correctness is vital, no approximations! and n is not THAT large that exponential is out of the question) algorithm to find the shopping assignments OR prove that the input does not allow an assignment where every participant is: 1) being shopped for by exactly one person and 2) shops for exactly one person other than himself

Algorithmically speaking:

GIVEN:
D, a simple digraph (no loops), where a node is a person and an edge from X to Y indicates X is willing to shop for Y

FIND:
D', a subset of D, where forall v in V, indegree(v) = outdegree(v) = 1. D' need not be connected (there is no guarantee D is). OR prove that given D, there is no satisfying D'.

CONSTRAINTS:
Must be correct. Time is key. A large but reasonable amount of space may be used. Bonus points if the algorithm can be randomized (or even produces different output if you start at a different node, so long as other constraints are still met).


Since I have a small n, I can play around with insane solutions like "select a random assignment, check for validity, if not valid repeat"... but it seems like there should be some sort of algorithm to do this, but at the same time, I wonder if maybe it is more difficult than it seems...

Source: http://community.livejournal.com/algorithms/67335.html

Date: 11/28/05     Keywords: no keywords

does anyone here know much about acoustic tracking algorithms? i'd like to put an implementation on a robot as part of a distributed surveillance project. ultimately, i'd like the following functionality:

• the robots automagically deploy themselves in some optimal manner (where optimal has yet to be defined.
• the robots go into a semi-sleep mode, powering down as much of their electronics as possible
• as the robots are in their semi-sleep mode, they have a set of n acoustic sensors and attached DSPs listening for unusual sounds. the sensors are arranged in some convenient pattern
• when a robot hears an unusual sound, it wakes up the other robots.
• the robots figure out who is nearest to the sound. that robot is dispatched to track the source of the sound. the remaining robots reconfigure themselves to maintain an optimal configuration.

what i'm hoping for is some suggestions on how to attack this problem. i know how to wake the robots up and compute the initial bearing and range guestimate. what i don't know how to do, however, is actively follow a sound. there are several papers (such as work done by rama chellapa at umd) on the more general subject of fusing acoustic and video sensing for tracking, but they are far more computationally demanding than what my platform will be able to handle. any suggestions on a reasonably simple approach to solving this will be greatly appreciated.

Source: http://www.livejournal.com/community/algorithms/66879.html

Date: 11/28/05     Keywords: no keywords

does anyone here know much about acoustic tracking algorithms? i'd like to put an implementation on a robot as part of a distributed surveillance project. ultimately, i'd like the following functionality:

• the robots automagically deploy themselves in some optimal manner (where optimal has yet to be defined.
• the robots go into a semi-sleep mode, powering down as much of their electronics as possible
• as the robots are in their semi-sleep mode, they have a set of n acoustic sensors and attached DSPs listening for unusual sounds. the sensors are arranged in some convenient pattern
• when a robot hears an unusual sound, it wakes up the other robots.
• the robots figure out who is nearest to the sound. that robot is dispatched to track the source of the sound. the remaining robots reconfigure themselves to maintain an optimal configuration.

what i'm hoping for is some suggestions on how to attack this problem. i know how to wake the robots up and compute the initial bearing and range guestimate. what i don't know how to do, however, is actively follow a sound. there are several papers (such as work done by rama chellapa at umd) on the more general subject of fusing acoustic and video sensing for tracking, but they are far more computationally demanding than what my platform will be able to handle. any suggestions on a reasonably simple approach to solving this will be greatly appreciated.

Source: http://community.livejournal.com/algorithms/66879.html

Date: 11/18/05     Keywords: no keywords

I think there's a service somewhere that if you put in your LJ's username, it splits out all clique(s) you're in. I am wondering how that is possible ? Isn't such algorithm not likely existed in polynomial time?



Let userA,userB,...,userC be the members of the *largest* clique in Livejournal, then when any of those members enters their username in the above mentioned service, the cliques they are in (including the largest clique) will be returned. And we know largest clique problem is NP-Hard ...

Source: http://www.livejournal.com/community/algorithms/66727.html

Date: 11/18/05     Keywords: no keywords

I think there's a service somewhere that if you put in your LJ's username, it splits out all clique(s) you're in. I am wondering how that is possible ? Isn't such algorithm not likely existed in polynomial time?



Let userA,userB,...,userC be the members of the *largest* clique in Livejournal, then when any of those members enters their username in the above mentioned service, the cliques they are in (including the largest clique) will be returned. And we know largest clique problem is NP-Hard ...

Source: http://community.livejournal.com/algorithms/66727.html

Date: 11/08/05     Keywords: no keywords

Graph Theory:

Why: So in Fleury's Algorithm there is a nice little line that says just don't do that if it's a bridge. but this has to be checked for every edge to be deleted. Where a bridge is an edge whose deletion separates a graph.

Want: an efficient way to check if an edge is a bridge

How:? is there something that runs in less than n^2?

Source: http://www.livejournal.com/community/algorithms/66260.html

Date: 11/08/05     Keywords: no keywords

Graph Theory:

Why: So in Fleury's Algorithm there is a nice little line that says just don't do that if it's a bridge. but this has to be checked for every edge to be deleted. Where a bridge is an edge whose deletion separates a graph.

Want: an efficient way to check if an edge is a bridge

How:? is there something that runs in less than n^2?

Source: http://community.livejournal.com/algorithms/66260.html

Date: 10/08/05     Keywords: programming

I am in need of a book about dynamic programming, and also perhaps one on algorithm design in general.

Any recommendations?

Source: http://www.livejournal.com/community/algorithms/65887.html

Date: 10/08/05     Keywords: programming

I am in need of a book about dynamic programming, and also perhaps one on algorithm design in general.

Any recommendations?

Source: http://community.livejournal.com/algorithms/65887.html

Date: 10/07/05     Keywords: programming

I'm really, really new to programming. I have to write a program in C that will crack a Caesar shift cipher. I'm stuck.
I've made a program that will get text a character at a time from a file and output it, also a character at a time, into another file, but that's it. I guess I need to somehow convert letters into numbers and back again, but I have no idea how!

Would anybody know how I should set about this? Please? :)

(I also know this is probably in entirely the wrong community, but it looks as though some of you might be able to help...?)

Source: http://www.livejournal.com/community/algorithms/65621.html