Home > Archive > Clipper > August 2004 > Scrambling a list
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Joe Wright 2004-08-21, 8:55 am |
| If this is Off Topic for the group, I appologize. I need some help
from xBASE programmers more experienced than I. The scenario..
I have a .dbf which is a list of members by family and a facility
that each member is assigned to. It might look like this..
first last fam fac
Michael Davis 2896 102
Mitch McGlynn 3706 74
Theresa McGlynn 3706 210
Mitchell McGlynn 3706 210
Megan McGlynn 3706 210
Patricia Doyle 3715 210
Sandra Ratliff 3712 342
Edgell Ratliff 3712 342
Lori Hayes 3713 74
David Hayes 3713 74
Mary Stoner 4777 40
Mary Harrison 22486 102
Thomas McGlynn 22751 391
Patricia Griffin 22751 391
Thomas McGlynn 22751 391
Connor McGlynn 22751 391
Kesley McGlynn 22751 391
Michaela McGlynn 22751 391
The task is to rearrange the rows such that neither fam or fac are
adjacent. Theresa McGlynn cannot follow Mitch for example because
their families are the same. Patricia Doyle cannot follow Megan
McGlynn because their facilities are the same.
I'm not sure it can be done at all. Until now, I can't. TIA.
--
Joe Wright mailto:joewwright@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
| |
| techno 2004-08-21, 8:55 am |
| On Sun, 15 Aug 2004 16:10:51 -0400, Joe Wright
<joewwright@comcast.net> wrote:
>If this is Off Topic for the group, I appologize. I need some help
>from xBASE programmers more experienced than I. The scenario..
>
>I have a .dbf which is a list of members by family and a facility
>that each member is assigned to. It might look like this..
>
>first last fam fac
>
>Michael Davis 2896 102
>Mitch McGlynn 3706 74
>Theresa McGlynn 3706 210
>Mitchell McGlynn 3706 210
>Megan McGlynn 3706 210
>Patricia Doyle 3715 210
>Sandra Ratliff 3712 342
>Edgell Ratliff 3712 342
>Lori Hayes 3713 74
>David Hayes 3713 74
>Mary Stoner 4777 40
>Mary Harrison 22486 102
>Thomas McGlynn 22751 391
>Patricia Griffin 22751 391
>Thomas McGlynn 22751 391
>Connor McGlynn 22751 391
>Kesley McGlynn 22751 391
>Michaela McGlynn 22751 391
>
>The task is to rearrange the rows such that neither fam or fac are
>adjacent. Theresa McGlynn cannot follow Mitch for example because
>their families are the same. Patricia Doyle cannot follow Megan
>McGlynn because their facilities are the same.
Sounds like a homework assignment to me. It is against my religion
to answer your problem. Hopefully everyone has good scruples.
>I'm not sure it can be done at all. Until now, I can't. TIA.
| |
| Dave Pearson 2004-08-21, 3:55 pm |
| * techno <out.there@somewhere.com>:
> Sounds like a homework assignment to me. It is against my religion to
> answer your problem. Hopefully everyone has good scruples.
Given that "homework problems" tend to be posted by hit-and-run posters (and
they're hardly ever posted to <URL:news:comp.lang.clipper> anyway) don't you
think that "good scruples" would run at least as far as you checking if the
OP was a regular of this group or not first? Here, let me do your homework
for you:
<URL:http://groups.google.com/groups?q=g...t%40comcast.net>
Good job I don't share your religion isn't it?
--
"Religion, whatever its consolations, makes for hideous governance."
John Lloyd, New Statesman
| |
| Dave Pearson 2004-08-22, 3:55 pm |
| * Joe Wright <joewwright@comcast.net>:
> I'm not sure it can be done at all. Until now, I can't. TIA.
It's a bit brute force and won't really scale very well but, in the absence
of a more elegant solution, how about generating lists of every possible
permutation and then searching for the first permutation that satisfies the
stated rules? Or is the volume of data too great for this to stand a chance
of working?
--
Dave Pearson | OSLib - Timeslice release functions.
http://www.davep.org/ | eg - Norton Guide reader for Linux.
http://www.davep.org/clipper/ | weg - Norton Guide reader for Windows.
http://www.davep.org/norton-guides/ | dgscan - DGROUP scanner for Clipper.
| |
| Stephen Quinn 2004-08-22, 3:55 pm |
| Joe
How many different familiy numbers??
How many different facility numbers??
How big a list??
You might not be enough family members for you to achieve it.
What I mean is if you have a family with 5 members you'll have to have at least
5 others from different families that don't have the same facility numbers.
Eg
> Thomas McGlynn 22751 391
> Michael Davis 2896 102
> Connor McGlynn 22751 391
> Mitch McGlynn 3706 74
> Kesley McGlynn 22751 391
> Theresa McGlynn 3706 210
> Michaela McGlynn 22751 391
Given the info you've supplied you'd probably have to use a brute force method.
--
HTH
Steve
| |
| Joe Wright 2004-08-22, 3:55 pm |
| techno wrote:
> On Sun, 15 Aug 2004 16:10:51 -0400, Joe Wright
> <joewwright@comcast.net> wrote:
>
[ my post is immediately up-thread ]
> Sounds like a homework assignment to me. It is against my religion
> to answer your problem. Hopefully everyone has good scruples.
>
It's not homework. It's hard stuff. No wonder you can't answer it.
--
Joe Wright mailto:joewwright@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
| |
| Ross McKenzie 2004-08-22, 3:55 pm |
| On Sun, 15 Aug 2004 20:02:42 -0500, "E.Fridman" <pm771@netscape.net>
wrote:
>Joe,
>
>Yes, it can be done. I mean such algorithms exist.
>http://www.staff.vu.edu.au/
Small world. The "vu" is Victoria University and is about 30 minutes
from me. I attended a single semester subject on the motorola 6809
microprocessor there back in ...cough, cough 1980 <g>.
Regards,
Ross McKenzie
ValuSoft
Melbourne Australia
valusoft AT optushome DOT com DOT au
| |
| techno 2004-08-22, 8:55 pm |
| On 15 Aug 2004 21:09:31 GMT, Dave Pearson <davep.news@davep.org>
wrote:
>* Joe Wright <joewwright@comcast.net>:
>
>
>It's a bit brute force and won't really scale very well but, in the absence
>of a more elegant solution, how about generating lists of every possible
>permutation and then searching for the first permutation that satisfies the
>stated rules? Or is the volume of data too great for this to stand a chance
>of working?
Ever heard of factorials?
F! of 18 is a bigger number than you'd want to make a list of? It's
like billions of billions of billions of billions. A big number.
| |
| Dave Pearson 2004-08-22, 8:55 pm |
| * techno <out.there@somewhere.com>:
> On 15 Aug 2004 21:09:31 GMT, Dave Pearson <davep.news@davep.org>
> wrote:
>
>
> Ever heard of factorials?
Yes; why do you think I included a disclaimer to that affect *twice* in the
above paragraph?
> F! of 18 is a bigger number than you'd want to make a list of? It's like
> billions of billions of billions of billions. A big number.
Unless I'm mistaken it's six quadrillion, four hundred and two trillion,
three hundred and seventy-three billion, seven hundred and five million,
seven hundred and twenty-eight thousand.
--
Dave Pearson | OSLib - Timeslice release functions.
http://www.davep.org/ | eg - Norton Guide reader for Linux.
http://www.davep.org/clipper/ | weg - Norton Guide reader for Windows.
http://www.davep.org/norton-guides/ | dgscan - DGROUP scanner for Clipper.
| |
| Peter B. Steiger 2004-08-22, 8:55 pm |
| On Mon, 16 Aug 2004 02:59:43 +0000, Ross McKenzie sez:
> Small world. The "vu" is Victoria University and is about 30 minutes
> from me. I attended a single semester subject on the motorola 6809
> microprocessor there back in ...cough, cough 1980 <g>.
{snicker} The poet/philosopher Michael Jagger put it best when he
wrote, "What a drag it is getting old." People don't believe me when I
tell them my high school class stored programs on paper tape, and my
freshman BASIC class in college was the last to use punch cards
exclusively for our assignments.
Of course, here I am telling this to a bunch of fellow Clipper dinosaurs.
It's the Javascript and C++ infants who can't grok punch cards (or
Motorola 6809 architecture, for that matter).
--
Peter B. Steiger
Cheyenne, WY
If you must reply by email, you can reach me by placing zeroes
where you see stars: wypbs_**3 at bornagain.com.
| |
| Peter B. Steiger 2004-08-22, 8:55 pm |
| On Sun, 15 Aug 2004 22:50:38 +0000, Ross McKenzie sez:
> 1. Calculate a 32 bit CRC of the trimmed firstname/trimmed last name,
> use the CRC as the index key and copy the records to a new dbf.
No need - it looks like the FAM field is a numeric representation of the
last name!
I can't see doing what he describes in fewer than two passes. If I
understand the problem correctly, each record would need to be "aware" of
its predecessor's values in order (no pun intended) to be displayed/sorted
non-adjacent to its neighbor's family/facility values.
I'm sure it's not a homework assignment, Joe, but it sure reads like one
in the sense of giving a stupid, pointless task to the programmer. What
on earth is the point of separating them out like that? Maybe if we had a
clearer understanding of the purpose or goal, we could hack together a
workable solution.
Is the data a fixed set that only needs to be "un-sorted" once, or do you
need to provide a mechanism for ensuring that new records added are also
not adjacent to a similar record? Would the facility ever be modified,
causing the record to need to be moved? (I'm assuming nobody would
arbitrarily switch families).
--
Peter B. Steiger
Cheyenne, WY
If you must reply by email, you can reach me by placing zeroes
where you see stars: wypbs_**3 at bornagain.com.
| |
| techno 2004-08-22, 8:55 pm |
| On 16 Aug 2004 12:54:23 GMT, Dave Pearson <davep.news@davep.org>
wrote:
>* techno <out.there@somewhere.com>:
>
>
>Yes; why do you think I included a disclaimer to that affect *twice* in the
>above paragraph?
>
>
>Unless I'm mistaken it's six quadrillion, four hundred and two trillion,
>three hundred and seventy-three billion, seven hundred and five million,
>seven hundred and twenty-eight thousand.
Sounds like billions of billions of billions of billions to me. Or you
could say 6.4023737x10^15 like calculators say it. Such a waste to
spell it out so far.
| |
| Alejandro 2004-08-22, 8:55 pm |
| /*
See below.
The wanted data is at the end of the mail
Sorry for the long post
Alejandro
** NOTE **
THIS CODE works, but is not optimized code !
*/
* I got your data inside OLD.DBF with
* APPEND FROM pepe.txt TYPE SDF
* I add a NUMERIC field of 4 position named ID to OLD.DBF
COPY FILE OLD.DBF TO WORK.DBF // backup because work will be destroyed
SELE 1
USE WORK
* Create empty dbf
COPY STRUCTURE TO LIST
SELE 2
USE LIST
SELE 1
*--- only for 1st Time --------
* We need the first rec for comparision purposes
nCurRec := 1
GOTO nCurRec
* Get needed fields
nOldFam := FAM
nOldFac := FAC
* copy current record to LIST.DBF
COPYFIELDS( nCurRec )
DELETE // current record
PACK
*--- only for 1st Time --------
DO WHILE LASTREC() > 0 // in WORK.DBF
? "record left: ", LASTREC()
nCurRec := INT( FT_RAND1( LASTREC() )) +1
GOTO nCurRec
IF FAM <> nOldFam // match family ?
IF FAC <> nOldFac // match facility ?
* lSuccess := .T.
* 2) Get New needed fields before deletion
nOldFam := FAM
nOldFac := FAC
* copy current record to LIST.DBF
COPYFIELDS( nCurRec )
DELETE // current record
pack
ENDIF
ENDIF
ENDDO
? "record left: ", LASTREC()
SELE 2
LIST ID, FIRST, LAST, FAM, FAC TO FILE output.txt
* After that if you want the original data, just index:
* SELE 2
* INDEX ON ID TO LIST1
QUIT
*------------------------------
FUNCTION COPYFIELDS( nCurRec )
*------------------------------
LOCAL nID, cFirst, cLast, nFam, nFac
// assumes you are stand, over the right record
nID = ID
cFirst = FIRST
cLast = LAST
nFam = FAM
nFac = FAC
SELE 2
APPEND BLANK
REPLACE ID WITH nID
REPLACE FIRST WITH cFirst
REPLACE LAST WITH cLast
REPLACE FAM WITH nFam
REPLACE FAC WITH nFac
COMMIT
SELE 1
GOTO nCurRec
RETURN 0
/*
This is one of the many output you can get
1 1 Michael Davis 2896 102
2 13 Thomas McGlynn 22751 391
3 8 Edgell Ratliff 3712 342
4 9 Lori Hayes 3713 74
5 18 Michaela McGlynn 22751 391
6 12 Mary Harrison 22486 102
7 3 Theresa McGlynn 3706 210
8 11 Mary Stoner 4777 40
9 4 Mitchell McGlynn 3706 210
10 14 Patricia Griffin 22751 391
11 2 Mitch McGlynn 3706 74
12 17 Kesley McGlynn 22751 391
13 10 David Hayes 3713 74
14 16 Connor McGlynn 22751 391
15 7 Sandra Ratliff 3712 342
16 6 Patricia Doyle 3715 210
17 15 Thomas McGlynn 22751 391
18 5 Megan McGlynn 3706 210
*/
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
| |
| Fred Zuckerman 2004-08-22, 8:55 pm |
| Would the following work? Air-Code...
Add a numeric field to the table named COUNT. Or create a copy. Now use the
fields
of FAM, FAC, and COUNT.
....
PrevFAM=""
PrevFAC=""
For i=1 To RECCOUNT()
Locate For FAM#PrevFAM .And. FAC#PrevFAC .And. COUNT=0
If .Not. EOF()
Replace COUNT With i
PrevFAM = FAM
PrevFAC = FAC
Else
? "Sorry. Too Many Records With FAM/FAC = " + PrevFAM + "/" + PrevFAC
Inkey(0)
Exit
Endif
Next
....
Now, index the table on COUNT.
Fred Zuckerman
"Joe Wright" <joewwright@comcast.net> wrote in message
news:0a6dnZTROendXoLcRVn-ow@comcast.com...
> If this is Off Topic for the group, I appologize. I need some help
> from xBASE programmers more experienced than I. The scenario..
>
> I have a .dbf which is a list of members by family and a facility
> that each member is assigned to. It might look like this..
>
> first last fam fac
>
> Michael Davis 2896 102
> Mitch McGlynn 3706 74
> Theresa McGlynn 3706 210
> Mitchell McGlynn 3706 210
> Megan McGlynn 3706 210
> Patricia Doyle 3715 210
> Sandra Ratliff 3712 342
> Edgell Ratliff 3712 342
> Lori Hayes 3713 74
> David Hayes 3713 74
> Mary Stoner 4777 40
> Mary Harrison 22486 102
> Thomas McGlynn 22751 391
> Patricia Griffin 22751 391
> Thomas McGlynn 22751 391
> Connor McGlynn 22751 391
> Kesley McGlynn 22751 391
> Michaela McGlynn 22751 391
>
> The task is to rearrange the rows such that neither fam or fac are
> adjacent. Theresa McGlynn cannot follow Mitch for example because
> their families are the same. Patricia Doyle cannot follow Megan
> McGlynn because their facilities are the same.
>
> I'm not sure it can be done at all. Until now, I can't. TIA.
> --
> Joe Wright mailto:joewwright@comcast.net
> "Everything should be made as simple as possible, but not simpler."
> --- Albert Einstein ---
| |
| Klas Engwall 2004-08-22, 8:55 pm |
| Peter,
>{snicker} The poet/philosopher Michael Jagger put it best when he
>wrote, "What a drag it is getting old." People don't believe me when I
>tell them my high school class stored programs on paper tape, and my
>freshman BASIC class in college was the last to use punch cards
>exclusively for our assignments.
BASIC? You must be a youngster <g>. I took a basic (lowercase!!!)
programming class after I had already finished my MBA. Fortran, PL/1
and Cobol were the primary languages taught then ... it was not until
several years later that BASIC classes started to appear. And yes,
puch cards were still the primary medium long after I graduated.
Those were the days ... <g>
Klas
-------
klas dot engwall at engwall dot com
Spammers, please use this address :-) mailto:postmaster@[127.0.0.1]
| |
| Norman Perelson 2004-08-22, 8:55 pm |
|
"Dave Pearson" <davep.news@davep.org> wrote in message
news:slrnci2hrt.8qi.davep.news@hagbard.davep.org...
> * techno <out.there@somewhere.com>:
>
trillion,[color=darkred]
million,[color=darkred]
>
> You like being overly judgmental don't you "techno"? Tell me what was
wasted
> and why it was a waste.
>
The techno' humour was wasted because "techno" did not sense it. But don't
let that worry you because I am sure many of us did.
--
Norman
| |
| Bert Kerkhof 2004-08-24, 8:55 am |
| Joe,
In a first pass, you need to count the records in a two-dimensional
frequency table. Say family is on the horizontal X-axis of this table, and
facility on the vertical Y-axis. After this pass you have an array
aCount[X,Y] filled.
To really find the optimum solution later on, sort this table so that the
most frequent families are in the left columns in the table and the most
frequent facilities in the upper rows. However, without sorting the result
will also be satisfying.
Then create an index on Str(Fac)+Str(Fam) for your persons Dbf so that you
can randomly s a person when you know his or hers Fac and Fam.
Then the second pass:
(1) Find out which cellcount in aCount[X,Y] is the highest. Say you find out
that the cell with family Xp, facility Yq has the highest score.
(2) S in the Dbf a person from this group, delete or mark the record and
write his or her name to your output list.
(3) Update the cellcount: aCount[Xp,Yq] := aCount[Xp,Yq] -1.
(4) Find out which cellcount in aCount[X,Y] now is the highest, excluding
row Yp and column Xp.
(5) The highest cellcount is zero? Then end the scrambled list and hope
there is no one left in row Yp or column Xp.
(6) Are there more cells that have the highest score? For each of them
calculate the ColumnTotal + RowTotal and choose the highest.
(7) Still having some cells that have an equally high score? When you have
the frequency table sorted, choose the cell with the highest Abs(X-Y). Then
you end up with the cells at the diagonal from upper-left to the
lower-right, where the diversity in Fac and Fam is the greatest.
(8) Continue with step (2)
I agree with Sali that you don't have to shuffle with the records. You can
do the intensive calculations with the array in memory.
Regards,
Bert Kerkhof
I remember the punch cards, but my study was sociology (with statistics).
| |
| hemant_pandya 2004-08-29, 1:36 pm |
| quote:
Originally posted by Joe Wright
If this is Off Topic for the group, I appologize. I need some help
from xBASE programmers more experienced than I. The scenario..
I have a .dbf which is a list of members by family and a facility
that each member is assigned to. It might look like this..
first last fam fac
Michael Davis 2896 102
Mitch McGlynn 3706 74
Theresa McGlynn 3706 210
Mitchell McGlynn 3706 210
Megan McGlynn 3706 210
Patricia Doyle 3715 210
Sandra Ratliff 3712 342
Edgell Ratliff 3712 342
Lori Hayes 3713 74
David Hayes 3713 74
Mary Stoner 4777 40
Mary Harrison 22486 102
Thomas McGlynn 22751 391
Patricia Griffin 22751 391
Thomas McGlynn 22751 391
Connor McGlynn 22751 391
Kesley McGlynn 22751 391
Michaela McGlynn 22751 391
The task is to rearrange the rows such that neither fam or fac are
adjacent. Theresa McGlynn cannot follow Mitch for example because
their families are the same. Patricia Doyle cannot follow Megan
McGlynn because their facilities are the same.
I'm not sure it can be done at all. Until now, I can't. TIA.
--
Joe Wright mailto:joewwright@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Dear Joe
Can U give an example of what type of list U want to generate from your test list
Hemant Pandya |
|
|
|
|