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

kappa_am · 2014-01-21 05:50:11

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:)

Bob · 2014-01-21 06:31:39

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)

kappa_am · 2014-01-21 08:14:21

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.

Bob · 2014-01-21 11:58:46

hi kappa_am

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

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

kappa_am · 2014-01-21 19:54:19

sorry for being vague. this is my best English
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

Bob · 2014-01-21 21:17:39

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?

I need new examples.

Bob

kappa_am · 2014-01-21 21:58:44

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}

bobbym · 2014-01-21 22:11:37

Hi;

gAr · 2014-01-21 22:32:02

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;
}

kappa_am · 2014-01-21 22:33:25

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

bobbym · 2014-01-21 22:38:10

Hi;

kappa_am · 2014-01-22 02:49:00

bobbym wrote:

Hi;

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

bobbym · 2014-01-22 02:50:23

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

kappa_am · 2014-01-22 04:12:53

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

bobbym · 2014-01-22 04:14:41

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

Math Is Fun Forum

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Board footer