|
Is there any fast algorithm for this:
K people sit at a table. Each person holds a number (hi) which means: some of his neighbour has a cap of height (hi). I want to count the number of combinations for setting people up at the table according to their height of their cups.
Example:
in:
6
2 6 4 5 3 5
out:
2
(We have two combinations which are 1 2 6 4 5 3 and 6 2 1 4 5 3)
Explanation:
We know that first person points on the second person and last person points on the penultimate person. The neighbour of the second person on the left is two, so his neighbour with height 4 should be on the right. Next we know that left neighbour of fifth person is 4, so his neighbour with height 3 should be on the right. We have two combinations to place 1, 6 cups (1,6 and 6, 1):
Visualisation:
2 6 4 5 3 5
X 2 X X 5 X
X 2 X 4 5 3
Possibilities: 1 2 6 4 5 3 or 6 2 1 4 5 3
Any suggestions or help would be greatly appreciated.
|
|
|
|
|
You need to specify the problem more clearly. Does everyone at the table have two neighbors, or do the two people at each end only have one neighbour? This may or may not affect the answer.
|
|
|
|
|
How do I select a column in access database imported in window form aplication, convert it to a array and then sort it using bubble sort?
|
|
|
|
|
Firstly this is the Algorithms forum, C# is further down. Secondly your question is far too generalised for a definitive answer. You can extract data from ACCESS by the use of SQL commands. How you process the result will depend on what data that is.
|
|
|
|
|
what is the Function of algorithm it self?
|
|
|
|
|
|
Hi,
I am new here. I hope I am doing this right. If not, please advise.
I signed up to handle a neighborhood project that involves distributing about 700 items to anyone in the neighborhood who wants them. I have created an Access database containing the items with details such as the size, weight, and condition (very good to poor). I also have a Google Sheet that I populated from the database. It has one row for each item. There are columns for each of the properties (description, size, weight, condition etc.). These are all read only (protected).
The first column is the selection column. In it, the neighbor can indicate whether they want that item or not. My current thinking is to let them enter a priority number (1-10) or leave it blank.
I will allow each neighbor to access a copy of that sheet and fill in their choices. When they are all done, I will lock the sheets and import the priority columns to Excel where I am more comfortable. I have the code roughed out that will do the actual allocations.
My remaining task is to devise an algorithm for allocating items that are selected by multiple people. I could just select randomly, but I'd like an algorithm that does the allocation as fairly as possible.
I realize that "fairly" is subjective.
I currently have about 20 people who have said they want some of the items. At least one person said they would take them all.
The algorithm will start by allocating all of the items that are selected by just one person.
My current thinking for the items selected by multiple people is to calculate some measure of the percentage of the items they requested that they have already been given. Suppose A & B both choose item 143, A has 20% of their requests, and B has 30% of theirs. I could then award that item to A or, since B has 3/2 as much of their selections as does A, I could generate a random number from 1-5 and award it to A if it's 1-3, and B if 4-5. Or I could skew it more in favor of A, the one with the lower percentage.
I'm not entirely happy with this algorithm for a couple of reasons. (1) It doesn't take into account the priority choice. What if A choose the item with a priority of 5, but B chose with with a priority of 1? (2) I'm not sure of it takes into account how many items each one chose. If B only chose 1 item but A chose 100, should that one go to B, because if not, they get nothing?
I would appreciate any suggestions for good ways to handle this.
Thanks
|
|
|
|
|
You do a draw for each item.
Assign each interested party a sequential number.
Generate a random number in the above range and assign the prize.
Most other methods will be called into question.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Let me see if I understand what you are suggesting. I have 15-20 "takers". I give each of then a number from 1-20, right so far? Then I pick the items one at a time and draw one of the taker numbers from a hat, like a Bingo wheel. Whichever number comes up, that person gets the item. Right?
So I have almost 700 items. Are you seriously suggesting that I have 700 "draws"? If I could manage to keep each draw to 30 seconds, which I doubt, that would take almost 6 hours.
Then there is the problem that most of the takers will only want a few items. So I'd have to go through the numbers after each draw and only put in the ones who want that item. Now we are well over minute for each draw and well over 12 hours for the whole disaster.
Plus I don't want to try and find a time when all 20 takers are available.
I have the items in a database and I have a Google Sheet containing the list of items that I can share with each taker. At their leisure, they can browse the list of items and indicate which they want. I will merge those choices into an Excel sheet that will execute my allocation algorithm.
All I need is the algorithm. The key feature is breaking ties.
I am working on a way to calculate the percentage of the choices each taker has received. If 2 or more takers want the same item, I will either award it to the3 one with the lowest percentage or generate a weighted random number based on those percentages.
|
|
|
|
|
I "seriously" thought you were saying you could program.
The "draw" is simply iterating through the list of items (a "for" loop); and then executing a "RAND" function if there are takers.
The "logistics" of "having takers available" has nothing to do with the "drawing program" and any "list" you may produce saying who got what.
It would take less than a second for 700 items.
You said:
1) You "have the items in a database". Don't you know how to read them? (Part 1)
2) They "indicate their choices" which you "merge, blah blah" (Part 2)
3) Rnd Function - Access
Your (output) list could even have a "second choice" if the winner did not show up to claim their prize. Yes, they claim them; you don't chase them down or wait for them after you "publish" the list of winners. You do intend to create a winner's list? Or is this word of mouth?
Oh ... and you don't "give" them a number; you "assign" it as you "merge them" (or whatever). You need a name, you assign a number that you can later randomly generate. I suggest 1,2,3,4, ... # of takers for "that" item.
If you knew anything about "indexes" (relative or otherwise), you wouldn't even need to assign a "physical" number; it would be based on "position"; assuming an unordered list.
Note, nowhere is there any extra "draw" time.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
modified 26-Aug-21 10:53am.
|
|
|
|
|
Wow! My programming skills may not be the best, but it's clear that you meet every geek stereotype, namely, social skills: non-existent.
|
|
|
|
|
What an interesting challenge !
Creating an "algorithm" for what I'd call "distributive social justice" requires you precisely define the logic of "who gets what." Of course, that logic can include introducing randomness.
Among the scenarios I'd want the algorithm to deal with:
0) "need" ... if you have a way to evaluate how much the person really needs the items, how "essential" the item is. Age ? Living alone vs, with others ? Income ? Health and access to health-care ?
1) "utility" ... if you have a way to evaluate how much the person can benefit from the items.
2) "greediness vs, modesty" ... does someone who wants everything with maximum intensity deserve more than those with fewer choices ?
3) "collateral benefits:" ... to what extent the items benefit the family, or community, of the receiver.
4) "reciprocity:" ... if you have a way to evaluate how much the person will contribute to your project.
And ... more, and more.
Given "human nature," whatever principles you define will probably anger some people ... unless you make the allocation "purely" random.
«The mind is not a vessel to be filled but a fire to be kindled» Plutarch
modified 29-Aug-21 0:20am.
|
|
|
|
|
I am a new and upcoming programmer. I want to know how can i advance my learning in data structures and algorithms.
|
|
|
|
|
Pick a language and learn about "collections".
Collections (C#) | Microsoft Docs
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
You should start with DFS, as it's very straightforward if you are familiar with recursion. BFS is slightly harder to digest for a beginner, as you'd need to understand the concept of queues first.
|
|
|
|
|
|
|
Hi All! I am new here.
I am wondering what is the name for the following algorithm I need to code. If I know the name I could find the algorithm.
1st example
Suppose I have a matrix
123
Aoo
Boo
C oo
D o
E oo Having it as an input I need to create an output like this:
ABx12, CEx23, Dx3 (x means cartesian product)
2nd example
12345
A oo o
B o o
Coo
Doo oo
Eo oo
F ooo should give me an output like
ABx25, CDx12, DEFx45, AFx3, Ex1
May you help me, please?
Thanks in advance,
Jacek
|
|
|
|
|
You need to guess a word. You are provided with a list of Words with the number of character matches at the right position.
Example
input {{"MOXTE",3} , {"AXCDG",0},{"MOQRT",2},{"FOUSE",4},{"POWER",1}}
return "MOUSE"
Explanation:
MOXTE MO##E 3 matches
AXCDG ##### 0 matches
MOQRT MO### 2 matches
FOUSE #OUSE 4 matches
POWER #O### 1 match
Result: MOUSE
I tried using brute force. Max heap is not working. Any leads?
|
|
|
|
|
Two things:
1) "It's not working" is one of the most useless problem descriptions we get: it tells us absolutely nothing about the problem. We don't know if you get an error message, or the wrong data, or even that that code compiles successfully!
Remember that we can't see your screen, access your HDD, or read your mind - we only get exactly what you type to work with.
So tell us what happens when you run that code, what you expected to happen, how you checked what happened. Help us to help you!
2) While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.
So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.
If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
Think about how you would do it manually: the number of "right letters" gives you lots of information.
AXCDG (0) - A is not the first, X is not the second, C is not the third, ...
FOUSE (4) - most of the letters are here, so look for identical letters in the others:
POWER (1) - Combined with FOUSE, the second is an O, the others aren't OP, W, E, or R
MOQRT (2) - Combined with FOUSE, and "2 is O", 1 is M
So ... MOUSE is the only possibility.
This isn't complicated, just think about it before leaping into code ...
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
With respect to this tree,
- What is the correct in-order traversal?
- U S T X C P Y R B A I G J F N H V T E D L
- U S T X C P Y R B A D E I G J F N H V T L
- What is the correct post-order traversal?
- U T S X P R Y C B D I J G N V T H F E L A
- U T S X P R Y C B I J G N V T H F E D L A
I evaluated both pairs. But some are saying 1-1 and 2-1 are correct, while others say 1-2 and 2-2 are correct. I'm confused. Which ones are actually correct?
modified 20-May-21 12:22pm.
|
|
|
|
|
1-2 and 2-2, maybe. I'll explain the reasoning, and why there is a "maybe".
Let's do the post-order one first, that's easier. OK so both answer start with "U T S X P R Y C B", so let's say we've just gone up out of B, and are looking at A right now (not "visiting" it yet though), so we recurse into L, which recurses into D, into E, into F, into G, into I, and then we come back up, so after B comes I, not D.
Or to put it in a different way: in a post-order traversal, a node is visited only after all its descendants, so there is no way D could be in the middle of this sequence, it has to be near the end. Only L and A could ever go after it.
The in-order question has two answers that start with "U S T X C P Y R B A", so let's say we're at A again, recursing into L, D, D's left child (null), then D itself, so it's the second answer. But here's why I added "maybe": "U S T X C P Y R B A" is not even the right sequence to start with, because it puts B after C but C is the right child of B so B should been visited before C. Both answers are wrong. But the first answer is worse: it gets more of the sequence wrong.
|
|
|
|
|
Thanks for your reply.
Below is my takeaway from your post.
Post-order traversal
Or to put it in a different way: in a post-order traversal, a node is visited only after all its descendants
Your statement quoted above was enough to clarify me about the post-order traversal. I believe, that makes the following series as the correct answer: U T S X P R Y C B I J G N V T H F E D L A
In-order traversal
According to your explanation, while traversal, if any node has a null left child, that node has to be visited right away as the immediate root node before moving down further. If I'm right, then, I think the following series is the correct answer: B U S T X C P Y R A D E I G J F N H V T L
|
|
|
|
|
priyamtheone wrote: B U S T X C P Y R A D E I G J F N H V T L
Yes this looks correct to me
|
|
|
|
|
I'm working on a UI which has a bunch of titles grouped under multiple categories(let's say list of movies). Let's say I have Category 1, Category 2, Category 3 etc., with each category having 20 movies under it. The problem is that some movies are repeated across categories and if they appear in the top 5 in multiple categories, then it looks bad in the UI, since it appears duplicated. The source of this categorization is out of my control and I'm just receiving this data from another service. My requirement is to look for duplicates across categories and if a movie already appeared in a higher ranked(based on order of display) category, penalise it and rank it down in the category. e.g., Movie1 appeared at Rank2 in Category1. Movie1 also appears at Rank4 in Category2. I want to move Movie1 to a much lower rank(say Rank15 or Rank20) in Category2 since it is already appearing at a higher rank in a previous category.
Problem:
--------
Category1:
1. Movie1
2. Movie2
3. Movie3
...
Category2:
1. Movie1
2. Movie4
3. Movie5
...
Category3:
1. Movie4
2. Movie6
3. Movie7
...
In the case above, I want to rank down Movie1 in Category2 to rank 10 or below since it already appears in Category1 at the same rank or above. Similarly, I want to rank down Movie4 in Category3 to be ranked down since it appears in a higher category at a higher rank.
I was thinking of assigning weights(in descending order) to categories and then calculating the score of each movie based on the rank+weight and then use this to rank down the repeating movies. I'm not an expert in algorithms, ranking etc, but I feel that this would be a common use case and there might already be solutions to such ranking problems. Can anyone guide me here?
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
