• Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.

Programming |OT| C is better than C++! No, C++ is better than C

U

usea

Member
TheFeedingHand said:
Now that we're talking IDEs and such, what OS do you prefer to work in? (for not work-related stuff)
Click to expand...
Usually I work in Windows since that's what I have installed. I find it a bit annoying to work in a VM, so I usually will do my editing in Windows and then sftp the file over to my Ubuntu VM when I save.
 
R

Randolph Freelander

Member
sans_pants said:
do they have a suggested curriculum?
Click to expand...

That's a very good question, and I don't have the answer to it, but I assume one could be found. At worst, I suspect if you go to their normal site, find the undergraduate/graduate program you're interested in, you'll find typical course sequences there.

Edit: Something like this, for example.
 
I

iapetus

Scary Euro Man
I'm the lone Linux holdout at our company - everyone else has gone Mac. I'd love to join them, but can't justify the money and don't want to support Apple while they're going through their full-on evil phase.
 
B

BomberMouse

Member
iapetus said:
I'm the lone Linux holdout at our company - everyone else has gone Mac. I'd love to join them, but can't justify the money and don't want to support Apple while they're going through their full-on evil phase.
Click to expand...

I made the switch almost a year ago and don't regret it. The build quality of the notebooks is so much better. I mostly work inside virtual machines anyway so there was little differences to me.
 
S

Splatt

Member
TheFeedingHand said:
Now that we're talking IDEs and such, what OS do you prefer to work in? (for not work-related stuff)
Click to expand...

I'd like to say Windows, but as someone already said, it's not really developer friendly.

I mostly use various Linux distro's on VM. I'm too cheap for Apple stuff. Currently, I'm working on Xubuntu.
 
C

chickdigger802

Banned
AppleSmack said:
What is the best metric to use to judge your progress?
Click to expand...

the smile or lack of on your boss's face.

It all depends really. I've translated a 20 page document in 2 days and my boss was pleased. I've fixed a defect that required changing a single line but took a day to figure out and the boss was pleased.

for the most part, as long as you seem productive, you will be fine.
 
O

opticalmace

Member
Linux vs. OS X for Python programming--any thoughts?

Looking for a new laptop. I mainly use numpy, scipy, some smaller packages etc. I have been using Ubuntu the last few years but would consider a Mac if it is equally convenient.

Is there a Mac repository? Something easy like "apt-get install" etc?
 
M

Magni

Member
^ python comes installed

TheFeedingHand said:
Now that we're talking IDEs and such, what OS do you prefer to work in? (for not work-related stuff)
Click to expand...

I use Windows, OS X, and Ubuntu daily, I like all three for various reasons, but I end up using OS X the most. The sexy MBA hardware has a lot to do with it though. I only like woking in Windows if it's with MS languages in VS (C#, maybe F# one day). Otherwise ST2 and iTerm 2 on my Air is all I need. Ubuntu is just for shits and giggles, I used it a lot more before I bought the Air earlier this year, I haven't used it outside of school since.

edit: anyone here doing Google Codejam? Qualification round starts in an hour: https://code.google.com/codejam/
 
T

TheFeedingHand

Member
MagniHarvald said:
^ python comes installed



I use Windows, OS X, and Ubuntu daily, I like all three for various reasons, but I end up using OS X the most. The sexy MBA hardware has a lot to do with it though. I only like woking in Windows if it's with MS languages in VS (C#, maybe F# one day). Otherwise ST2 and iTerm 2 on my Air is all I need. Ubuntu is just for shits and giggles, I used it a lot more before I bought the Air earlier this year, I haven't used it outside of school since.

edit: anyone here doing Google Codejam? Qualification round starts in an hour: https://code.google.com/codejam/
Click to expand...

Yup, even though I don't think I'll make it past the Qualification round lol.
 
H

ha1f

Member
opticalmace said:
Linux vs. OS X for Python programming--any thoughts?

Looking for a new laptop. I mainly use numpy, scipy, some smaller packages etc. I have been using Ubuntu the last few years but would consider a Mac if it is equally convenient.

Is there a Mac repository? Something easy like "apt-get install" etc?
Click to expand...

both are fine (i'd rather live on linux, but the mac hardware is so nice). the only python issue i can remember having on os x was with pyglet/amd64 which might not even be a problem anymore.

for python packages, you should probably be living in a pip/virtualenv world anyway, right? so that stuff is pretty predictable.

for general packages, there's homebrew and macports. i come from a freebsd background and i have been getting along fine with homebrew.
 
B

BomberMouse

Member
ha1f said:
both are fine (i'd rather live on linux, but the mac hardware is so nice). the only python issue i can remember having on os x was with pyglet/amd64 which might not even be a problem anymore.

for python packages, you should probably be living in a pip/virtualenv world anyway, right? so that stuff is pretty predictable.

for general packages, there's homebrew and macports. i come from a freebsd background and i have been getting along fine with homebrew.
Click to expand...

I endorse this reply.
 
S

Slavik81

Member
Harpuia said:
||=== project2, Debug ===|
In function `int main()':|
28|error: no matching function for call to `Employeemgmt::fillArray(int&, int&, std::string&, std::string&, std::string&, std::string&, std::string&)'|
8|note: candidates are: void Employeemgmt::fillArray(int, std::string, std::string, std::string, std::string, std::string)|
||=== Build finished: 1 errors, 0 warnings (0 minutes, 0 seconds) ===|

As you can see, the function does exist but for some reason it thinks I'm calling a function with the same parameters, but the parameters are called by reference for some reason.

uhhhh durr I just figured it out. forgot to initialize a parameter in my class definition. God I hate it when it's something as simple as that. :/
Click to expand...
You can ignore how it assumed they were references. It didn't know what function you were trying to call so it just guessed at what the signature might have been. The existence of references, implicit type conversions and inheritance limit how well the compiler can guess what function you meant to call based on the parameters.

Glad you figured it out. The key was hidden in the argument lists in the error. You were passing 2 int parameters followed by 5 string parameters, but your function took 1 int parameter followed by 5 string parameters.
 
J

JaMarco

Member
Hey guys, I'm stuck on an assignment. Does anyone know how to go about making this program (using Java or C++)?
Consider a "word" as any sequence of capital letters A-Z (not limited to just "dictionary words"). For any word with at least two different letters, there are other words composed of the same letters but in a different order (for instance, stationarily/antiroyalist, which happen to both be dictionary words; for our purposes "aaiilnorstty" is also a "word" composed of the same letters as these two). We can then assign a number to every word, based on where it falls in an alphabetically sorted list of all words made up of the same set of letters. One way to do this would be to generate the entire list of words and find the desired one, but this would be slow if the word is long.

Write a program which takes a word as a command line argument and prints to standard output its number. Do not use the method above of generating the entire list. Your program should be able to accept any word 25 letters or less in length (possibly with some letters repeated), and should use no more than 1 GB of memory and take no more than 500 milliseconds to run. Any answer we check will fit in a 64-bit integer.

Sample words, with their rank:

ABAB = 2
AAAB = 1
BAAA = 4
QUESTION = 24572
BOOKKEEPER = 10743

Your program will be judged on how fast it runs and how clearly the code is written. We will be running your program as well as reading the source code, so anything you can do to make this process easier would be appreciated.
Click to expand...
To tell the truth, I don't completely understand the question. I'm not sure how the "words" are supposed to be ordered and what algorithm to use to order them. Any help would be appreciated, thanks.
 
M

Milchjon

Member
Case said:
Hey guys, I'm stuck on an assignment. Does anyone know how to go about making this program (using Java or C++)?

To tell the truth, I don't completely understand the question. I'm not sure how the "words" are supposed to be ordered and what algorithm to use to order them. Any help would be appreciated, thanks.
Click to expand...

I won't be able to help you with the algorithm, but the way I understand it, you take the input string, jumble it so you get every possible combination of the characters in it, and then order all of them alphabetically. You then check the position of your initial string in that list.

Like for instance, if the initial word is BAAA:

1. AAAB
2. AABA
3. ABAA
4. BAAA

-> Output: 4

(I don't know if this helps your understanding at all)

Edit: I think that's actually a common exercise, so there should be like a billion implementations out there. Haven't checked though.
 
B

BomberMouse

Member
Case said:
Hey guys, I'm stuck on an assignment. Does anyone know how to go about making this program (using Java or C++)?

To tell the truth, I don't completely understand the question. I'm not sure how the "words" are supposed to be ordered and what algorithm to use to order them. Any help would be appreciated, thanks.
Click to expand...

What's not to get? you just have to calculate how many "words" can be created with a given set of characters then order that set of elements lexicographically and print the position of the word they gave you.

For example, ABBA, all the words you can make, ordered, are:
AABB
ABAB
ABBA
BAAB
BABA
BBAA

So ABBA => 3

EDIT: Beaten :(
 
A

arit

Member
Case said:
Hey guys, I'm stuck on an assignment. Does anyone know how to go about making this program (using Java or C++)?

To tell the truth, I don't completely understand the question. I'm not sure how the "words" are supposed to be ordered and what algorithm to use to order them. Any help would be appreciated, thanks.
Click to expand...

It is just sorted in alphabetical order, so a full list of the first three examples would be:

Code: 
[B]AAAB 1[/B]
AABA 2
ABAA 3
[B]BAAA 4[/B]

Code: 
WRONG

So if a word consists of n_0,n_1,.....,n_m characters, just compare character at n_i of both words until they differ.

EDIT: it's late >_<
 
M

Milchjon

Member
For those more experienced, I guess the first, simple way to speed up the algorithm for the above problem would be to first sort the characters, and then only create the list until you actually reach the word, instead of creating the whole list and then checking where the word is at?

So for AAAB, the list would only be:

1. AAAB,

For ABAA:

1. AAAB
2. AABA
3. ABAA

instead of the full four-word list in both cases?

Or am I on the wrong way there?
 
B

BomberMouse

Member
Milchjon said:
For those more experienced, I guess the first, simple way to speed up the algorithm for the above problem would be to first sort the characters, and then only create the list until you actually reach the word, instead of creating the whole list and then checking where the word is at?

So for AAAB, the list would only be:

1. AAAB,

For ABAA:

1. AAAB
2. AABA
3. ABAA

instead of the full four-word list in both cases?

Or am I on the wrong way there?
Click to expand...

IMHO the best way would be just to traverse the tree of posible words, ordering the branches and calculating the number of elements on each branch as needed.
 
L

luoapp

Member
Milchjon said:
For those more experienced, I guess the first, simple way to speed up the algorithm for the above problem would be to first sort the characters, and then only create the list until you actually reach the word, instead of creating the whole list and then checking where the word is at?

So for AAAB, the list would only be:

1. AAAB,

For ABAA:

1. AAAB
2. AABA
3. ABAA

instead of the full four-word list in both cases?

Or am I on the wrong way there?
Click to expand...

You are not supposed to generate any list. It should be "calculated" directly.
 
C

Chris R

Member
Well the easy bit is you know there will be some count of n! words before you even get to the letter your word starts with (IE for questions you don't even need to care about the exxxxxx or ixxxxxx or nxxxxxx or oxxxxxx words). Once you have that as a nice baseline you should be able to use some fancy math to calculate the exact position of your word pretty quickly. The tricky part is the duplicate letters, like in the bookkeeper example as you shouldn't count beeekkoopr 24 times.
 
S

StrangeADT

Banned
squidyj said:
Alright, so in our final assignment we're working with threads and system calls and signals and whatnot. I've finished everything except for one part of the assignment we need to create as many threads as we can in 3 seconds, 10 times over. We do this twice, once using pthread_create and once using clone or vfork.

My pthread implementation works fine but my clone implementation segfaults on occasion. This is what the relevant code looks like.

Code: 
#define STACK_SIZE 4096
#define TEST_COUNT 10
...

int clone_child(void *param)
{
	return 1;
}

void test_clone(int list[])
{
	int i, temp, flags;
	char *end, *stack;
	flags = (CLONE_VM | CLONE_THREAD | CLONE_SIGAND);
	end = malloc(STACK_SIZE);
	if(end == NULL)
		return;
	stack = end + STACK_SIZE;
	for(i = 0; i < TEST_COUNT; i++)
	{
		cont = 1;
		//SIGALRM sets cont to 0
		alarm(3);
		while(cont);
		{	
			//arguments in order, function, stack address, flags, function arguments
			temp = clone(clone_child, stack, flags, NULL)
			if(temp > 0)
			{
				list[i] += 1;
			}
		}
		printf("Iteration %d spawned %d threads n", (i + 1), list[i]);
	}
}

...
Click to expand...

Well the difference between fork and clone is that memory space is shared between the parent and child so everytime you clone, each of the clones is usin the same stack that you provided and will modify it on entry and return. Depending on timing of your print statement it may or may not reproduce the error. I suspect if you comment out the loop it may actually happen more often or even regularly but I have to be honest that I have not used clone myself so I'm unfamiliar with its behavior.

Also, google search clone and read about it. Good description here: linux.die.net/man/2/clone.
 
A

A Human Becoming

More than a Member
Can someone explain to me something in Python? I put a # where my questions are. This code works (on Codecademy at least):
Code: 
lloyd = {
    "name": "Lloyd",
    "homework": [90, 97, 75, 92],
    "quizzes": [88, 40, 94],
    "tests": [75, 90]
}
alice = {
    "name": "Alice",
    "homework": [100, 92, 98, 100],
    "quizzes": [82, 83, 91],
    "tests": [89, 97]
}
tyler = {
    "name": "Tyler",
    "homework": [0, 87, 75, 22],
    "quizzes": [0, 75, 78],
    "tests": [100, 100]
}

students = [lloyd, alice, tyler]
def average(score):
    average_value = sum(score) / len(score)
    return average_value
def get_average(student):
    final_score = ((average(student['homework'])*0.1) + (average(student['quizzes'])*0.3) + (average(student['tests'])*0.6)) 
#This is where I'm mainly confused. Somehow it manages to identify student by name, even though it hasn't be defined. There's nothing proceeding it called student whether in a function or in a for loop. It works with 'students' as well. Can the name just be whatever as it's just a label for the dictionaries?
    return final_score
def get_letter_grade(score):
    score = round(score)
    if score >= 90:
        return "A"
    elif 80 <= score < 90:
        return "B"
    elif 70 <= score < 80:
        return "C"
    elif 60 <= score < 70:
        return "D"
    else:
        return "F"
print get_letter_grade(get_average(lloyd)) 
#So this means student represents the three dictionaries where lloyd is one?
def get_class_average(students):
    class_average = 0 
#Do you have to put class average = 0? Must you give it a integer before it can do calculations?
    for pupil in students:
        class_average += get_average(pupil)
    return class_average/len(students)
 
D

dutchguyjack

Member
A Human Becoming said:
Can someone explain to me something in Python? I put a # where my questions are. This code works (on Codecademy at least):
Code: 
lloyd = {
    "name": "Lloyd",
    "homework": [90, 97, 75, 92],
    "quizzes": [88, 40, 94],
    "tests": [75, 90]
}
alice = {
    "name": "Alice",
    "homework": [100, 92, 98, 100],
    "quizzes": [82, 83, 91],
    "tests": [89, 97]
}
tyler = {
    "name": "Tyler",
    "homework": [0, 87, 75, 22],
    "quizzes": [0, 75, 78],
    "tests": [100, 100]
}

students = [lloyd, alice, tyler]
def average(score):
    average_value = sum(score) / len(score)
    return average_value
def get_average(student):
    final_score = ((average(student['homework'])*0.1) + (average(student['quizzes'])*0.3) + (average(student['tests'])*0.6)) 
#This is where I'm mainly confused. Somehow it manages to identify student by name, even though it hasn't be defined. There's nothing proceeding it called student whether in a function or in a for loop. It works with 'students' as well. Can the name just be whatever as it's just a label for the dictionaries?
    return final_score
def get_letter_grade(score):
    score = round(score)
    if score >= 90:
        return "A"
    elif 80 <= score < 90:
        return "B"
    elif 70 <= score < 80:
        return "C"
    elif 60 <= score < 70:
        return "D"
    else:
        return "F"
print get_letter_grade(get_average(lloyd)) 
#So this means student represents the three dictionaries where lloyd is one?
def get_class_average(students):
    class_average = 0 
#Do you have to put class average = 0? Must you give it a integer before it can do calculations?
    for pupil in students:
        class_average += get_average(pupil)
    return class_average/len(students)
Click to expand...



Question 1: This is where I'm mainly confused. Somehow it manages to identify student by name
Answer: That's because get_average is a function which is called by get_class_average. You pass the parameter/dictionary "students" to get_class_average, which iterates through the list of students (for pupil in students: ...). Each iteration "pupil" will represent one of the students. When "pupil" is then passed to get_average, we're actually passing Lloyd, Alice or Tyler to get_average.

Question 2: So this means student represents the three dictionaries where lloyd is one?
Answer: Students is a dictionary that contains dictionaries. In other words, it's just a list of students.

Question 3: Do you have to put class average = 0? Must you give it a integer before it can do calculations?
Answer: In most cases yes. Because when class average is calculated, we're adding the value that get_average returned to the variable classaverage. If that variable is undefined (e.g. it has no value, not even 0), we'd get a calculation of classaverage = undefined + 88.5. Haven't coded in python for a while so I'm not sure how Python would respond to that, but usually you get an error.
 
A

A Human Becoming

More than a Member
dutchguyjack said:
Question 1: This is where I'm mainly confused. Somehow it manages to identify student by name
Answer: That's because get_average is a function which is called by get_class_average. You pass the parameter/dictionary "students" to get_class_average, which iterates through the list of students (for pupil in students: ...). Each iteration "pupil" will represent one of the students. When "pupil" is then passed to get_average, we're actually passing Lloyd, Alice or Tyler to get_average.
Click to expand...
You can still print final_score without the get_class_average function. Why does it work before that function is added then?
Question 2: So this means student represents the three dictionaries where lloyd is one?
Answer: Students is a dictionary that contains dictionaries. In other words, it's just a list of students.
Click to expand...
I think I understand that.
Question 3: Do you have to put class average = 0? Must you give it a integer before it can do calculations?
Answer: In most cases yes. Because when class average is calculated, we're adding the value that get_average returned to the variable classaverage. If that variable is undefined (e.g. it has no value, not even 0), we'd get a calculation of classaverage = undefined + 88.5. Haven't coded in python for a while so I'm not sure how Python would respond to that, but usually you get an error.
Click to expand...
I know people have done it without defining class_average, but most people seem to define it. It just sounds like an unnecessary step, but I suppose it adds clarity.
 
D

dutchguyjack

Member
A Human Becoming said:
You can still print final_score without the get_class_average function. Why does it work before that function is added then?
Click to expand...
That's because final_score is a variable that is local to get_average, it doesn't exist outside of its scope and is calculated in get_average.

Try replacing this line:
Code: 
print get_letter_grade(get_average(lloyd))

with this:
Code: 
print get_letter_grade(get_average(students))

And you'll find it doesn't work. That's because get_average only works for a student, not for a list of students. final_score just refers to the average of that particular student, not to that of all students.

I know people have done it without defining class_average, but most people seem to define it. It just sounds like an unnecessary step, but I suppose it adds clarity.
Click to expand...

It may be possible in Python, but I'm not sure so I'm not going to say one or the other. But it's good practice to always define all your variables, even if a language allows you not to. That's to make sure you retain good coding habits across all languages you code in, and you won't find yourself facing some nasty problems switching over from one to the other.

In general, explicit code is good code. As long as your program isn't performance critical, don't worry about its performance, just worry about doing things clearly and sensibly.
 
0

0xCA2

Member
i haven't coded in weeks ( but did a small program today ). Its just that I feel that when I have general studies classes, if I really dig deep into programming it'll take away from those classes (like, causing me to fail), but I mostly procrastinate those classes anyway, so i just end up on the internet...

Point being, I always read that good programmers have this insatiable desire to program 24/8. Can I never be a good programmer because I don't code 24/7? When I do get really into it, I am really prolific, but I can fall off easily as well.

Note that I can accept that I'll never be a good programmer. Also I just started a year ago.

Also, I'm really slumping in my math class, though I'm usually good at it/ I usually like it. It's just hard for me to put in the motivation this semester to study, for some reason. I heard good programmers get straight As in math class easily. What say you?
 
H

hawkshockey11

Banned
Doing my first hackathon tomorrow!

Pretty excited, and we have a solid idea. I may posting for some guidance as I have never worked with computer vision before. Please standby, ProgrammingGaf.
 
U

usea

Member
Antroid said:
i haven't coded in weeks ( but did a small program today ). Its just that I feel that when I have general studies classes, if I really dig deep into programming it'll take away from those classes (like, causing me to fail), but I mostly procrastinate those classes anyway, so i just end up on the internet...

Point being, I always read that good programmers have this insatiable desire to program 24/8. Can I never be a good programmer because I don't code 24/7? When I do get really into it, I am really prolific, but I can fall off easily as well.

Note that I can accept that I'll never be a good programmer. Also I just started a year ago.

Also, I'm really slumping in my math class, though I'm usually good at it/ I usually like it. It's just hard for me to put in the motivation this semester to study, for some reason. I heard good programmers get straight As in math class easily. What say you?
Click to expand...
The best of the best (way less than 1%) might do this. As in the kind of people who name algorithms and invent famous things. But don't get hung up on it at all. It's not even a little important.

Also, a good chucnk of the cs majors who I went to school with failed at least one math class. Probably about 30%.
 
S

Snowdrift

Member
Math classes aren't that difficult. It's just the coursework in CS classes is so heavy that studying for mathematics takes a back-seat, and before you know it, finals week pops up, and you are half as prepared as you should be. At least that has been my experience.
 
T

toddhunter

Member
Antroid said:
Point being, I always read that good programmers have this insatiable desire to program 24/8. Can I never be a good programmer because I don't code 24/7? When I do get really into it, I am really prolific, but I can fall off easily as well.

...

Also, I'm really slumping in my math class, though I'm usually good at it/ I usually like it. It's just hard for me to put in the motivation this semester to study, for some reason. I heard good programmers get straight As in math class easily. What say you?
Click to expand...

It is kind of in reverse. Remember, good programming is a difficult thing to do. What this means is if you are a good programmer? There is a very good chance that you are going to be pretty good at everything including maths and will have the drive to throw yourself into whatever you choose to do.

You'll be a good programmer if you want to be so and put in the work. Some people just need to work harder than others to get there.
 
U

usea

Member
Case said:
Hey guys, I'm stuck on an assignment. Does anyone know how to go about making this program (using Java or C++)?

To tell the truth, I don't completely understand the question. I'm not sure how the "words" are supposed to be ordered and what algorithm to use to order them. Any help would be appreciated, thanks.
Click to expand...
This question is really tricky! Even if it didn't include duplicate letters it'd be tricky. To help you start looking, the problem relates to the "factoradic" number system. It's a system that's useful in mapping between an integer N and the Nth permutation in lexicographical order. This process is often called ranking and unranking. However, the explanations of this process you'll most commonly find assume that the elements in the input distinct (ie: a set). It gets a lot harder with repeating elements.

Here are some words that will help googling: factoradic permutation lexicographical repeat

Here is the best explanation I know of, for finding the Nth permutation (or finding N, given a permutation) in lexicographical order. http://www.keithschwarz.com/interesting/code/?dir=factoradic-permutation
But again, it assumes no duplicates.
 
S

squidyj

Member
StrangeADT said:
Well the difference between fork and clone is that memory space is shared between the parent and child so everytime you clone, each of the clones is usin the same stack that you provided and will modify it on entry and return. Depending on timing of your print statement it may or may not reproduce the error. I suspect if you comment out the loop it may actually happen more often or even regularly but I have to be honest that I have not used clone myself so I'm unfamiliar with its behavior.

Also, google search clone and read about it. Good description here: linux.die.net/man/2/clone.
Click to expand...

I'm not sure why you're talking about my print statement. It sounds like you think my threads are picking up at the point they were created as if it was a fork, but that's not what is happening or at the very least it shouldn't be.

Case said:
Hey guys, I'm stuck on an assignment. Does anyone know how to go about making this program (using Java or C++)?

To tell the truth, I don't completely understand the question. I'm not sure how the "words" are supposed to be ordered and what algorithm to use to order them. Any help would be appreciated, thanks.
Click to expand...

I can see how to do it relatively efficiently. starting at the end of the string with only one character to 'choose' you so far have a rank of 0 (number 1, top rank) and have only 1 permutation. furthermore you have a total of 1 character to choose from and it's weight is 1, store this information somewhere

working backward through the string for each character, add this character to the list, if we let n be the number of permutations of our previous substring then
this substring will have n * (n+1) / k substrings where k is the count for the character we added at this point.

If you look at the alphabetical ordering of this character compared to the list of available characters then you take the sum of the counts of all of the characters that precede the current character alphabetically, multiply them by n. add this value to your current rank.

repeat this process and you should have a rank that is off by 1. add 1.

Example:

Let our string be apple

starting at e we have 1 permutation and 1 instance of e. we have rank 0

looking at l, we add p to the list of characters, giving it a count of 1
this means at this point there are 2 permutations
also, l is after e so we take 2 / 2 * 1 = 1
our rank is 1

next up is p, p is new too so it gets a count of 1
2 * 3 / 1 = 6 permutations for 'ple'
p is worse than both l and e so 6 / 3 * 2 = 4
our rank is now 5

a second p, p's count goes up to 2
6 * 4 / 2 = 12 permutations for 'pple'
again, p is worse than both l and e
12 / 4 * 2 = 6
our rank is now 11

finally the a, a is better than everybody
12 * 5 / 1 = 60
a is better than everyone, we add nothing to our rank

our final rank is 11

lets check the 'pple' substring because checking all 60 permutations for apple will be tiresome

elpp, eplp, eppl, lepp,
lpep, lppe, pelp, pepl,
plep, plpe, ppel, pple

that looks like a complete list of 12 to me, and with pple as the final element in that list, number 12, 11+1. Also, since apple starts with a, it can't lose rank so
apple must have the same rank, and it does.

since it works this time it must work every time :p

You can save a division by multiplying the new permutation by (n+1) after the rank at this point has been calculated. which is also preferrable because it means for the last (and thus largest) number of permutations you can avoid calculating that whole number, which could, in all probability wind up breaking your 64 bit barrier even if you're given a string with a rank that's under the limit.
 
You must log in or register to reply here.

Similar threads

Satya Nadella: Annual letter to stockholders. Content on new platforms will continue
4 5 6 7 8
352
21K
noob smokes replied
Ken Kutaragi is the Greatest 'emperor' Of All Time and remains SIE's only true visionary
Opinion 2 3 4
156
16K
GAF machine replied
Nvidia reports record earnings, profits on growth in AI and gaming
Business Analysis Hardware 2
68
6K
FStubbs replied
Dave the Diver |OT| Life is better, down where's it wetter
|OT| Indie 2 3
137
13K
Impotaku replied
WWE and Endeavor (UFC) announce 21 billion dollar deal.
40
3K
thefool replied
Top Bottom