Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2014-01-21 05:50:11

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Picking a number of a set of numbers (discrete mathematics)

hi all,

I have a bunch of numbers; they are constructed of digits without repetition, and in this numbers a digit is always greater lower value digits. This numbers are categorized according to the its number of digit; in each category all possible numbers are exist.
here a simple example:

assume the numbers constructed of 1, 2, 3, 4, 5 and they are catagorized as follow according to number of digits:

1-digit: 1, 2, 3, 4, 5
2-digit: 12, 13, 14, 15, 23, 24, 25, 34, 35, 45
3-digit: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345
4-digit: 1234, 1235, 1245, 1345, 2345
5-digit: 12345
the question is: how I can find a number by knowing the category and the number of its place in row. for example by knowing category number 2 and sequence number 7, I have to obtain: 25

since it becomes cumbersome at higher orders, I need to formulate the procedure. a formula or a algorithm is appreciated.

Thank you:)

Offline

#2 2014-01-21 06:31:39

Bob
Administrator
Registered: 2010-06-20
Posts: 10,058

Re: Picking a number of a set of numbers (discrete mathematics)

hi kappa_am

This looks like the binomial theorem.  Have a look here:

http://www.mathsisfun.com/algebra/binomial-theorem.html

You see your numbers 1 4 6 4 1 about half way down the page.

Note:  If you have 7 numbers and want all the two number pairs, the total is 21 = (7 x 6)/2

Bob

Last edited by Bob (2014-01-21 06:34:26)


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#3 2014-01-21 08:14:21

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Picking a number of a set of numbers (discrete mathematics)

thank you for your reply.
I have read all the page. but, beats me. I know the number of figures in each category. the problem is developing a formula or a algorithm to find a figure using its category number and a number that indicates its location in the category. for example having number of category 3 and location number 4 I have to reach to 134.
I couldn't understand how to use binomial theorem to develop required algorithm. i will be grateful if you provide more information.

Offline

#4 2014-01-21 11:58:46

Bob
Administrator
Registered: 2010-06-20
Posts: 10,058

Re: Picking a number of a set of numbers (discrete mathematics)

hi kappa_am

If you know the answer is 134 then I'm wrong;  it cannot be the binomial.  sad

In your post one example you had 1,2,3,4 and 5 and made all possible 1-digit, 2-digit .... 5-digit numbers where a digit from the set may only be used once and the digits are in ascending order of size.  You got 1 then 4 then 6 then 4 then 1 as results.  This looked to me  like the binomial.

But now you have location number 4 (?? what is a location number??) and category 3 (??what is a category ??)

It would be tedious to list all 134 answers, but please give a few so I can understand what you are doing.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#5 2014-01-21 19:54:19

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Picking a number of a set of numbers (discrete mathematics)

sorry for being vague. this is my best English smile
for example I have five figure: 1, 2, 3, 4, 5. I can make numbers with 1 or 2 or 3 or...5 digit. the laws that must be considered in building this numbers are 1- a specific figure has not be used  twice or more in a number ( maximum once can be used). 2- always higher order digits have greater value than lower order value ( I can have 123 but I never have 321 or 213). using  these laws I can construct following numbers which are categorized according to its number of digits:
1-digit: 1, 2, 3, 4, 5
2-digit: 12, 13, 14, 15, 23, 24, 25, 34, 35, 45
3-digit: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345
4-digit: 1234, 1235, 1245, 1345, 2345
5-digit: 12345
these are all possible numbers when I have figures 1,2,...,5
Now, I know the category number of a specific number and its number in that category. for example I know the number belongs to 2-digit category and is 6th number in that category. knowing these I have to find 24. I like to find an algorithm or a formula for this procedure.
I have to declare that number with more than 1-digit can be a vector. for example i=24 can be i(1)=4 and i(2)=2

Thank you

Offline

#6 2014-01-21 21:17:39

Bob
Administrator
Registered: 2010-06-20
Posts: 10,058

Re: Picking a number of a set of numbers (discrete mathematics)

hi kappa_am

Let's decide on some words.

eg. Start Set = {1, 2, 3, 4, 5}

n-digit = another set with every number containing n digits

eg.  3-digit = {123, 124, 125, 134, 135, 145, 234, 235, 245, 345}

n-digit is a category

location = position in the n-digit set for a number

eg.  In the 3-digit set above with location = 4   => number = 134

THE PROBLEM.

We know that number = 24.  => n-digit = 2-digit

We know location = 4

Thus 2-digit = {**, **, **, 24, **, **, .........}

There are many Start Sets that would have 24 in them.

{1, 2, 3, 4, 5} ?

2-digit = {12, 13, 14, 15, 23, 24,  .....}  location = 6

{1, 2, 3, 4 } ?

2-digit = {12, 13, 14, 23, 24, 34}  location = 5 

{1,2,4} ?

2-digit = {12, 14, 24}  location = 3

{2,4} ?

2-digit = {24}  location = 1

I cannot find any solution with location = 4.

Where am I going wrong?  dizzy

I need new examples.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#7 2014-01-21 21:58:44

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Picking a number of a set of numbers (discrete mathematics)

location number 4 belongs to example I explain in post #3
in example of post #5, the location is 6 and the category is 6.
about last post, we don't know the number, we just know the category and the number location in that category. an we like to find the number according to this information.
our categories are always consist of all possible numbers not a subset for example 2-digit category: 2-digit = {12, 13, 14, 15, 23, 24, 25, 34, 35, 45}
furthermore the figures always start from 1 and are successive for example {1,2,3} we never have {2,3,4} or {1,3,4}

Offline

#8 2014-01-21 22:11:37

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Picking a number of a set of numbers (discrete mathematics)

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2014-01-21 22:32:02

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Picking a number of a set of numbers (discrete mathematics)

Hi kappa_am,

You mean you want to lexicographically generate the combinations and pick the one you want?

There are some algorithms, here's a C code I have used from rosettacode

#include <stdio.h>
 
typedef unsigned long marker;
marker one = 1;
int k=0;
 
void comb(int pool, int need, marker chosen, int at, int s)
{
	if (pool < need+at) return; 
 
	if (!need) {
		for (at = 0; at < pool; at++)
			if (chosen & (one << at)) 
                if (k == s-1) 
                    printf("%d", at+1);
        k++;
		return;
	}
	comb(pool, need - 1, chosen | (one << at), at + 1, s);
	comb(pool, need, chosen, at + 1, s); 
}
 
int main()
{
	comb(5, 2, 0, 0, 6);
	return 0;
}

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

#10 2014-01-21 22:33:25

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Picking a number of a set of numbers (discrete mathematics)

I have found a way but it's too time consuming.
lets explain it by an example. our digit is {1,2,3,4,5} and in 3-digit category I like to find 9th number.
we now the smallest member of each category is a number with 1 in highest value digit and the lower digits values increment by 1 for example first member of 2-digit category is 12 and first member of 3-digit category is 123. Knowing this lets start solving the problem.
123
add the sequence number-1 to first digit; if it becomes more than number of our set numbers add 1 to first and second digit. do result minus 6. repeat this till the result become 0. In adding procedure treat the digits based on its location for example first digit is based on 5 and when it becomes 6 it overflows, the second digit is based on 4 and so on
back to example:
first digit is 3 + 8 = 11 -6 = 5. the number becomes 123+011=134
first digit is 4 + 5= 9 -6 = 3 . the number becomes 134+011=145
first digit is 5 + 3= 8 -6 = 2 . the number becomes 145+011=234
first digit is 4 + 2= 6 -6 = 0 . the number becomes 234+011=245

and yes the 9th number is 245
3-digit: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345
I have checked with another conditions and set with higher number of figures and it is ok but in set with high number of members when I look for a number at the end of the category it becomes cumbersome. is there any better solution?

Dear Bobbym, I am able to program by Fortran and C++. I will check Banker's sequence

Offline

#11 2014-01-21 22:38:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Picking a number of a set of numbers (discrete mathematics)

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#12 2014-01-22 02:49:00

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Picking a number of a set of numbers (discrete mathematics)

bobbym wrote:

Hi;

I am able to write a algorithm that maps binary numbers to a subset, very efficiently. the problem is somewhat different. faint

Offline

#13 2014-01-22 02:50:23

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Picking a number of a set of numbers (discrete mathematics)

You must map them in a particular ordering. That is exactly what a "Bankers Sequence" is.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#14 2014-01-22 04:12:53

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Picking a number of a set of numbers (discrete mathematics)

I looked at banker's sequence. don't you think that my method is more efficient than that method?
in banker's sequence all possibilities are checked but I think my method reach to answer very soon.
please let me know your idea
thanks

Offline

#15 2014-01-22 04:14:41

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Picking a number of a set of numbers (discrete mathematics)

You do not have to generate the entire sequence.

This is the best explanation I can find of it I know of.

http://www.thelowlyprogrammer.com/2010/ … ts-of.html


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB