Re: Re: [algogeeks] Required O(n) Algorithm
Yeah we cant use count sort, as we dont know the range of elements here... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Required O(n) Algorithm
@Rahul: Please explain how you are going to use a counting sort with the
original poster's data.
Dave
On Wednesday, April 18, 2012 8:12:41 AM UTC-5, Rahul Kumar Patle wrote:
> use counting sort..
> it gives linear time complexity...
> first step of counting sort is the same as you have mentioned in
> question...
>
>
> On Wed, Apr 18, 2012 at 6:37 PM, VIHARRI wrote:
>
>> Can anybody give an O(n) algorithm for the following problem.
>>
>> Suppose if we have an array, I would like to construct an array with the
>> elements which specify their corresponding position in the sorted array.
>>
>> For example if the array is { 0.87, 0.04, 0.95, 0.12, 0.36 } then the
>> sorted array would be { 0.04, 0.12, 0.36, 0.87, 0.95 }.
>> Then output array would be {3, 0, 4, 1, 2 }.
>>
>> Hope I'm clear...
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/NH1P0aIguFEJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Thanks and Regards:
> Rahul Kumar Patle
> M.Tech, School of Information Technology
> Indian Institute of Technology, Kharagpur-721302, India
> Mobile No: +91-8798049298, +91-9424738542
> patlerahulku...@gmail.com
> rahulkumarpa...@yahoo.com
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/yeTCwQ-WsOwJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: dp problem
F[n] = number of ways to tile a 4-by-n grid G[n] = number of ways to tile a 4-by-n grid with top-right and bottom-right squares uncovered H[n] = number of ways to tile a 4-by-n grid with bottom-right 2 squares uncovered = number of ways to tile a 4-by-n grid with top-right 2 squares uncovered if n >= 2, the right end of any tiling can be two vertical dominoes (F[n-1] ways) horz, horz vert (H[n-1] ways) horz, vert, horz (G[n-1] ways) vert, horz, horz (H[n-1] ways) 4 horizontal dominoes (F[n-2] ways) F[n] = F[n-1] + G[n-1] + 2*H[n-1] + F[n-2]; For G: the right end can be a vertical domino (F[n-1] ways) or two horizontal dominoes => top & bottom are horz = G[n-2] G[n] = F[n-1] + G[n-2]; For H: the right end can be a vertical domino (F[n-1] ways) or two horizontal dominoes (H[n-1] ways) H[n] = F[n-1] + H[n-1]; F[0] = 1, F[1] = 1, G[0] = 0, G[1] = 1, H[0] = 0, H[1] = 1 Hope it helps !! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: string comparsion
I would recommend to just get rid of the first "non-numerical" characters
and use atoi function. Something like:
char *get_first_num(char *s)
{
while( (*s < '0') || (*s >'9') )
++s;
return s;
}
int main()
{
char *a = "b005b";
cout << atoi(get_first_num(a)) << endl;
return 0;
}
So then you can compare your numbers as:
atoi(get_first_num(a)) < atoi(get_first_num(b))
On Tuesday, 17 April 2012 20:18:13 UTC-7, Abhishek wrote:
>
> Hi,
>
> I need to compare string into following way. Can anyone provide me some
> insight or algorithm in c++.
>
> For example:
>
> "a5" < "a11"- because 5 is less than 11
> "6xxx < 007asdf"- because 6 < 7
> "00042Q < 42s" - because Q < s alphabetically
> "6 8" < "006 9" - because 8 < 9
>
>
>
> Thx in advance
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/LMz9srnKdE4J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Required O(n) Algorithm
Hi, Hashing can be used. Perfect/Universal hashing resolves collision and makes retrievals in constant time. for n elements it gives O(n) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Required O(n) Algorithm
use counting sort..
it gives linear time complexity...
first step of counting sort is the same as you have mentioned in question...
On Wed, Apr 18, 2012 at 6:37 PM, VIHARRI wrote:
> Can anybody give an O(n) algorithm for the following problem.
>
> Suppose if we have an array, I would like to construct an array with the
> elements which specify their corresponding position in the sorted array.
>
> For example if the array is { 0.87, 0.04, 0.95, 0.12, 0.36 } then the
> sorted array would be { 0.04, 0.12, 0.36, 0.87, 0.95 }.
> Then output array would be {3, 0, 4, 1, 2 }.
>
> Hope I'm clear...
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/NH1P0aIguFEJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks and Regards:
Rahul Kumar Patle
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302, India
Mobile No: +91-8798049298, +91-9424738542
patlerahulku...@gmail.com
rahulkumarpa...@yahoo.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String comparison
Hi Abhishek, You can use following string comparison function "strcmplogicalw" you can refer http://msdn.microsoft.com/en-us/library/windows/desktop/bb759947%28v=vs.85%29.aspx Regards, Shivakumar On Wed, Apr 18, 2012 at 9:16 AM, abhishek wrote: > Hi, > > I need to compare string into following way. Can anyone provide me some > insight or algorithm in c++. > > For example: > > "a5" < "a11"- because 5 is less than 11 > "6xxx < 007asdf"- because 6 < 7 > "00042Q < 42s" - because Q < s alphabetically > "6 8" < "006 9" - because 8 < 9 > > ** ** > > Thx in advance > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Required O(n) Algorithm
@Viharri: A solution seems to require an O(n) sorting algorithm, and since
sorting by comparison is O(n log n), the algorithm must use one of the
other types of O(n) sorting algorithms. Since the data are not integers in
a bounded range, I suggest using a radix sort, carrying along an array of
indices. I.e., form an array of indices {0, 1, 2, ..., n-1} and perform the
same data movements on it as on the original data. When the original data
are sorted, then the array of indices will be the desired result.
Dave
On Wednesday, April 18, 2012 8:07:33 AM UTC-5, VIHARRI wrote:
> Can anybody give an O(n) algorithm for the following problem.
>
> Suppose if we have an array, I would like to construct an array with the
> elements which specify their corresponding position in the sorted array.
>
> For example if the array is { 0.87, 0.04, 0.95, 0.12, 0.36 } then the
> sorted array would be { 0.04, 0.12, 0.36, 0.87, 0.95 }.
> Then output array would be {3, 0, 4, 1, 2 }.
>
> Hope I'm clear...
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/evd8iLvP2CUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Required O(n) Algorithm
Can anybody give an O(n) algorithm for the following problem.
Suppose if we have an array, I would like to construct an array with the
elements which specify their corresponding position in the sorted array.
For example if the array is { 0.87, 0.04, 0.95, 0.12, 0.36 } then the
sorted array would be { 0.04, 0.12, 0.36, 0.87, 0.95 }.
Then output array would be {3, 0, 4, 1, 2 }.
Hope I'm clear...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/NH1P0aIguFEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: String comparison
Thx for in detail description and some insight
On Wed, Apr 18, 2012 at 5:40 PM, Gene wrote:
> You can't solve a problem like this with only examples of <. A
> complete definition is necessary. For example, what do you do with
> "a1" <>? "2b"
> Report "mismatch?"
> What do you do with
> "1 abc" <>? "2 2"
> Do you report < or mismatch?
> Here is one of infinitely many complete definitions consistent with
> your examples:
> 1. Split each string into lists of maximal tokens consisting of all
> decimal digits or all letters. White space separates tokens but is
> otherwise ignored. Anything other than digits, letters, and
> whitespace is counted as end of string.
> 2. Call these lists A and B. Compare them pairwise. If Ai and Bi
> are
> both strings of letters, compare them lexically using UTF-8 order.
> If
> Ai and Bi are all digits, compare them numerically. Continue until
> you find an inequality between a pair and report this immediately,
> ignoring the rest of the string. If you find a pair with types
> (letters or digits) that don't match, or if one token list is shorter
> than the other, report "nothing." Otherwise if you run out of pairs,
> report equal.
> Here is code that is probably pretty close to this definition. Tasks
> like this are easier if you split them up into a token scanning step
> and a processing step. I've done that here.
>
> #include
> #include
>
> // Scanner return values.
> #define END 0
> #define DIGITS 1
> #define ALPHA 2
>
> // Find the start and end of the first token
> // beginning at *start, ignoring initial white space.
> int scan(char **start, char **end)
> {
> char *p = *start;
> while (isspace(*p)) ++p;
> if (isdigit(*p)) {
>*start = p;
>do ++p; while (isdigit(*p));
>*end = p;
>return DIGITS;
> }
> if (isalpha(*p)) {
>*start = p;
>do ++p; while (isalpha(*p));
> *end = p;
>return ALPHA;
> }
> return END;
> }
>
> // Return the non-negative value of the string
> // starting at p and ending at the char before end.
> int int_value(char *p, char *end)
> {
> int x = 0;
> while (p != end)
>x = 10 * x + (*p++ - '0');
> return x;
> }
>
> // Possible comparison values.
> #define LT -1
> #define EQ 0
> #define GT 1
> #define NOTHING 2
>
> // Compare the strings starting at xp and ending
> // one char before x_end where x is a or b.
> int string_compare(char *ap, char *a_end,
> char *bp, char *b_end)
> {
> while (ap < a_end && bp < b_end) {
> int diff = *ap++ - *bp++;
>if (diff < 0) return LT;
>if (diff > 0) return GT;
> }
> if (bp < b_end) return LT;
> if (ap < a_end) return GT;
> return EQ;
> }
>
> // Compare tokens in strings a and b.
> int compare(char *a, char *b)
> {
> char *a_end, *b_end;
>
> while (1) {
>int a_scan = scan(&a, &a_end);
>int b_scan = scan(&b, &b_end);
> if (a_scan != b_scan) return NOTHING;
>if (a_scan == END) return EQ;
>if (a_scan == DIGITS) {
> int a_val = int_value(a, a_end);
> int b_val = int_value(b, b_end);
> if (a_val < b_val) return LT;
> if (a_val > b_val) return GT;
>}
>else if (a_scan == ALPHA) {
> int cmp = string_compare(a, a_end, b, b_end);
> if (cmp != EQ) return cmp;
>}
>a = a_end;
> b = b_end;
> }
> }
>
> int main(void)
> {
> char *s[] = {
>"a5", "a11",
>"6xxx", "007asdf",
>"00042Q", "42s",
>"6 8", "006 9",
> };
> int i;
> for (i = 0; i < sizeof s / sizeof s[0]; i += 2) {
>int cmp = compare(s[i], s[i + 1]);
>printf("%s %c %s\n", s[i], "<=>?"[cmp + 1], s[i + 1]);
> }
> return 0;
> }
>
>
> On Apr 17, 11:46 pm, "abhishek" wrote:
> > Hi,
> >
> > I need to compare string into following way. Can anyone provide me some
> > insight or algorithm in c++.
> >
> > For example:
> >
> > "a5" < "a11"- because 5 is less than 11
> > "6xxx < 007asdf"- because 6 < 7
> > "00042Q < 42s" - because Q < s alphabetically
> > "6 8" < "006 9" - because 8 < 9
> >
> > Thx in advance
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: String comparison
You can't solve a problem like this with only examples of <. A
complete definition is necessary. For example, what do you do with
"a1" <>? "2b"
Report "mismatch?"
What do you do with
"1 abc" <>? "2 2"
Do you report < or mismatch?
Here is one of infinitely many complete definitions consistent with
your examples:
1. Split each string into lists of maximal tokens consisting of all
decimal digits or all letters. White space separates tokens but is
otherwise ignored. Anything other than digits, letters, and
whitespace is counted as end of string.
2. Call these lists A and B. Compare them pairwise. If Ai and Bi
are
both strings of letters, compare them lexically using UTF-8 order.
If
Ai and Bi are all digits, compare them numerically. Continue until
you find an inequality between a pair and report this immediately,
ignoring the rest of the string. If you find a pair with types
(letters or digits) that don't match, or if one token list is shorter
than the other, report "nothing." Otherwise if you run out of pairs,
report equal.
Here is code that is probably pretty close to this definition. Tasks
like this are easier if you split them up into a token scanning step
and a processing step. I've done that here.
#include
#include
// Scanner return values.
#define END 0
#define DIGITS 1
#define ALPHA 2
// Find the start and end of the first token
// beginning at *start, ignoring initial white space.
int scan(char **start, char **end)
{
char *p = *start;
while (isspace(*p)) ++p;
if (isdigit(*p)) {
*start = p;
do ++p; while (isdigit(*p));
*end = p;
return DIGITS;
}
if (isalpha(*p)) {
*start = p;
do ++p; while (isalpha(*p));
*end = p;
return ALPHA;
}
return END;
}
// Return the non-negative value of the string
// starting at p and ending at the char before end.
int int_value(char *p, char *end)
{
int x = 0;
while (p != end)
x = 10 * x + (*p++ - '0');
return x;
}
// Possible comparison values.
#define LT -1
#define EQ 0
#define GT 1
#define NOTHING 2
// Compare the strings starting at xp and ending
// one char before x_end where x is a or b.
int string_compare(char *ap, char *a_end,
char *bp, char *b_end)
{
while (ap < a_end && bp < b_end) {
int diff = *ap++ - *bp++;
if (diff < 0) return LT;
if (diff > 0) return GT;
}
if (bp < b_end) return LT;
if (ap < a_end) return GT;
return EQ;
}
// Compare tokens in strings a and b.
int compare(char *a, char *b)
{
char *a_end, *b_end;
while (1) {
int a_scan = scan(&a, &a_end);
int b_scan = scan(&b, &b_end);
if (a_scan != b_scan) return NOTHING;
if (a_scan == END) return EQ;
if (a_scan == DIGITS) {
int a_val = int_value(a, a_end);
int b_val = int_value(b, b_end);
if (a_val < b_val) return LT;
if (a_val > b_val) return GT;
}
else if (a_scan == ALPHA) {
int cmp = string_compare(a, a_end, b, b_end);
if (cmp != EQ) return cmp;
}
a = a_end;
b = b_end;
}
}
int main(void)
{
char *s[] = {
"a5", "a11",
"6xxx", "007asdf",
"00042Q", "42s",
"6 8", "006 9",
};
int i;
for (i = 0; i < sizeof s / sizeof s[0]; i += 2) {
int cmp = compare(s[i], s[i + 1]);
printf("%s %c %s\n", s[i], "<=>?"[cmp + 1], s[i + 1]);
}
return 0;
}
On Apr 17, 11:46 pm, "abhishek" wrote:
> Hi,
>
> I need to compare string into following way. Can anyone provide me some
> insight or algorithm in c++.
>
> For example:
>
> "a5" < "a11" - because 5 is less than 11
> "6xxx < 007asdf" - because 6 < 7
> "00042Q < 42s" - because Q < s alphabetically
> "6 8" < "006 9" - because 8 < 9
>
> Thx in advance
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
