|
Coding an ending mask (xyz) and then having it ignored seems illogical.
To me, * represent 0 or one or many; ? represents any one match.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Thanks for your opinion. I tend to agree. Happy holidays!
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
You too! And best in the new year.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Traditionally, the * wildcard in a regular expression is "zero or more instances of the preceding character", so the regex "abc*def" would match "abcdef", "abccccdef" and even "abdef" (0 c's), but not "abccxccdef". It might even match "Hello abcccdef there", depending on whether the regex is considered to be anchored or not. In a traditional regex the '.' wildcard is to match any character. However, if you're writing your own regex parser, you're free to place any meaning on the wildcard characters you want.
The functionality you seem to be trying to reproduce seems very like unix file globbing. If that's what you're trying to do - and you are on a unix like system, you probably have access to glob(3) , which does all the heavy lifting for you. There's probably similar functionality for windows.
But maybe you're writing a regex parser for your own purposes. In which case you're free to make up the rules you want. Either way, I'd expect any literals in the regex to be present in any matches found.
Keep Calm and Carry On
|
|
|
|
|
Thank you for your input. I'm actually not going for regular expressions, just simple wildcard matching like in MS-DOS.
Happy holidays!
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
String must start with abc and end with xyz
I also think that abc*xyz should match these:
abcxyxyz
abcxxyz
abcxyz
abcxxxxyyyyxyz
Add them to your unit tests.
The nice thing with this algorithm is that there is not a lot of state to track.
Very simple to implement in any language.
|
|
|
|
|
Slightly more complex if you want to extend it to a path of (back)slash separated directory levels with a directory name '**' indicating zero or more directory levels. I find this so useful that I would recommend that you include it from the very beginning. (Assuming, of course, that your wildcard routine is intended for file names, or similarly structured name strings.)
|
|
|
|
|
If * matched any character, then it would already match a slash.
You would have to make * not match a slash to need ** as another symbol.
I have seen and used the ** in a lot of utilities including Ant xml file sets. I have never had to write the logic for it, though.
|
|
|
|
|
Try MSDOS 5.0.
That's what I expect. Nothing more. Nothing less.
Bastard Programmer from Hell
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
If you write a matching routine for file/path names, you should at least as an option treat the path separators differently. For a general matching routine, the (set of) separator character(s) should be a parameter, so the same routine can be used in different contexts, e.g. different file systems.
I guess that writing a match for ** that doesn't use recursion would require more effort and the code would be more difficult to comprehend than to do it recursively. I wouldn't ever consider flattening that recursive matching routine I use in my code. (But of course, like in all recursion, I take care to reduce the stack frame to a minimum.)
|
|
|
|
|
The original post does not mention file system anywhere.
I was thinking more in terms of a pure programming exercise.
For traversing directory structures, I use a Visitor pattern with methods of beginDir/endDir/foundFile.
This allows easy reuse of the recursive algorithm across a dozen utilities that process file trees.
Keeps the stack lean for the recursion, any bloat ends up in the Visitor’s heap memory. (Including a few utilities that needed their own stack data structure to perform their job)
|
|
|
|
|
Here edges is a String array representing a set of space separated integer pair elements e.g. "e1 e2" where 0 < e1!=e2 <= n
n is an integer, let's say ranging 0 < n <= 100000
public int sumSqrtCeil(int n, String[] edges){
...
List<Set<Integer>> edgeSetList = "converted first edges element to set of Integer"
for(int i=1;i<edges.length;i++){
Set<Integer> nodeDuo = "converted this edges element to set of Integer"
boolean found = false;
for(Integer e : nodeDuo){
for (Set<Integer> edgeSet : edgeSetList) {
found = edgeSet.contains(e);
if (found) {
break;
}
}
if(found) break;
}
if(!found){
indexOfEdgeSetList++;
edgeSetList.add(nodeDuo);
}
else{
edgeSetList.get(indexOfEdgeSetList).addAll(nodeDuo);
}
}
Set<Integer> linkedNodes =
for(int i=1;i<=n;i++){
if(!linkedNodes.contains(i)) output+=1;
}
output += edgeSetList.stream().mapToInt(integers -> (int) Math.ceil(Math.sqrt(integers.size()))).sum();
return output;
}
As per my understanding (updated) complexity should be-
O( O(A) * O(B) * O(C) + O(D) + O(E) )
O( O(edges.length) * O(2) * O(n/2) + O(n) + O(edges.length) )
O( O(edges.length) * O(n) + O(n) + O(edges.length) ) //constant removed
O( O(n*edges.length) + O(n) + O(edges.length) ) //evaluate
O( O(n^3) + O(n) + O(n^2) ) //evaluate
O( O(n^3) ) //taking biggest factor
O(n^3) - Final Time Complexity.
where,
O(edges.length) = O( n! / 2! * (n-2)! ) = O( ( n * (n-1)) / 2 ) = O( n^2 - n / 2) ==> O(n^2)
Please feel free to share also consider me a complete noob for Algorithm. Just started learning formally.
modified 24-Nov-21 1:01am.
|
|
|
|
|
You might have a better chance of getting a response if you stated the algorithm in the more general style of most textbooks rather than in C#, which not all readers understand.
|
|
|
|
|
Thanks for advise.
I am not a computer science grad, Let me have a look at an Algo book to study to update my question.
Perhaps I may not need this forum to answer this question in the process.
|
|
|
|
|
Tried to update and make simpler to understand
|
|
|
|
|
Micronaut here (Microverse Student)
To get the complexity of this algorithm is actually quite simple, just check if there is an existing nested for loops and if those for loops actually depend on the input.
For example:
for(... input.length) {
for(...input2.length) {
}
}
this code's complexity will be the length of input1 * length of input2. and if they are the same, it will be the length^2. which is what we note by n².
|
|
|
|
|
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.
|
|
|
|