Կոնֆիգուրացիոն ֆայլերի գեներացիա

Խնդիրը

Տրված է պարամետրերի ցուցակ և ամեն մի պարամետրի համար տրված է նրա արժեքների բազմությունը։ Այդ արժեքները կարող են լինել իդենտիֆիկատորներ, տողեր, իրական կամ ամբողջ թվեր, բայց որևէ պարամետր կարող է ունենալ միայն մեկ տիպի արժեքներ։ Այլ կերպ ասած՝ պարամետրի տիպը ֆիքսվում է։ Օրինակ, կարող են տրված լինել հետևյալ պարամետրերը․

A = {a, b, c}
B = {"s1", "u2", "v3", "z4"}
C = {1.2, 3.4}

Պետք է գեներացնել կոնֆիգուրացիոն ֆայլեր, որոնցից ամեն մեկը պարունակի տրված պարամետրերի մեկական արժեք։ Օրինակ, հետևյալները կարող են լինել այդպիսի ֆայլերի օրինակներ․

file1.cfg       file2.cfg       file3.cfg

A = a           A = c           A = c
B = "s1"        B = "z4"        B = "z4"
C = 1.2         C = 1.2         C = 3.4

Պահանջվում է կա՛մ գեներացնել ֆայլերի բոլոր հնարավոր տարբերակները, կա՛մ գեներացնել տրված քանակով և չկրկնվող պարունակությամբ ֆայլեր։

Պարզ է, որ խնդրի էությունը տրված պարամետրերի արժեքների բազմությունների դեկարտյան արտադրյալի հաշվարկն է։ Բայց ինչպե՞ս դա անել, երբ նախապես ոչինչ հայտնի չէ․ ո՛չ պարամետրերի քանակը, ո՛չ ամենի մի պարամետրի թույլատրելի արժեքների քանակը։ Այս հարցերին պատասխանելուց առաջ տամ մի քանի սահմանումներ։

Սահմանումներ

Դիցուք տրված է \(M=\left\langle S_n\right\rangle\) բազմությունների խումբը։ Այդ բազմությունների դեկարտյան արտադրյալ է կոչվում բոլոր \((x_1,x_2,\ldots,x_n)\) կարգավորված հավաքածուների բազմությունն է, որտեղ \(x_i\in S_i\)․

\[D=\prod_{k = 1}^n S_k = \left\{{\left({x_1, x_2, \ldots, x_n}\right): \forall k \in \mathbb{N}^*_n: x_k \in S_k}\right\}\]

Հեշտ է նկատել, որ դեկարտյան արտադրյալի բազմության տարրերի քանակը հավասար է արտադրիչ բազմությունների տարրերի քանակների արտադրյալներին։

\[|D|=\prod_{k=1}^n |S_k|\]

Թող արտադրյալ բազմության ամեն մի կարգավորված \((x_1,x_2,\ldots,x_n)\) n-յակի ինդեքս կոչվի այն \((r_1,r_2,\ldots,r_n)\) կարգավորված n-յակը, որի \(r_k\) տարրը ցույց է տալիս, որ \(x_k\) տարրը \(k\)-րդ բազմության \(r\)-րդ տարրն է։

Բոլոր հնարավոր տարբերակները

Tcl լեզվի ցուցակի տեսքով սահմանեմ արտադրիչ բազմությունների ցուցակը․

set params {{A {ayb ben gim}} {B {alpha beta gamma delta}} {C {1 2}}}

Այս ցուցակի ամեն մի տարրը նորից ցուցակ է և բաղկացած է երկու բազմության անունից ու արժեքների բազմությունից։ Այս արժեքների բազմությունն էլ իր հերթին տրված է ցուցակի տեսքով։

Այնուհետև հաշվեմ մի ցուցակ, որը պարունակում է արտադրիչ բազմությունների երկարությունները։ Նաև միաժամանակ հաշվեմ այդ ցուցակի տարրերի արտադրյալը։

set powers [list]
foreach e $params { lappend powers [llength [lindex $e 1]] }
set allelems [expr [join $powers { * }]]

Բոլոր հնարավոր տարբերակները գեներացնելու եմ վերը սահմանված հաջորդական ինդեքսների կառուցումով։ Եվ դրա համար index փոփոխականին վերագրում եմ զրոյական ինդեքսը։

set index [list]
for {set i 0} {$i < [llength $powers]} {incr i} { lappend index 0 }

Կազմակերպում եմ մի պարամետրով ցիկլ՝ արտադրյալ բազմության տարրերի քանակով, որի պարամետրը մասնակցելու է գեներացվող ֆայլի անունի մեջ։

for {set k 0} {$k < $allelems} {incr k} {

Այս պահին, երբ ունեմ զրոյական ինդեքսը, կարող եմ գեներացնել այդ ինդեքսին համապատասխան ֆայլը։ Դրա համար պետք է զուգահեռաբար անցնել ինդեքսի տարրերով ու արտադրիչ ցուցակներով, և ամեն մի ցուցակից ընտրել ու ֆայլում արտածել ինդեքսին համապատասխան տարրը։

  # generate one case
  set out [open case_${k}.cfg w] 
  foreach i $inx s $params {
    puts $out "[lindex $s 0] = [lindex [lindex $s 1] $i]"
  }
  close $out

Հիմա պետք է հաշվել հաջորդ ինդեքսը։ Դրա համար ընթացիկ ինդեքսին «գումարում» եմ մեկ։ Այս գործողությունը շատ նման է դիրքային գումարման գործողությանը, բայց կատարվում է ձախից աջ։

  #  calculate next index
  set res [list]
  set m 1
  foreach i $inx p $powers {
    set t [expr $i + $m]
    lappend res [expr {$t == $p ? 0 : $t}]
    set m [expr {$t == $p ? 1 : 0}]
  }
  set inx $res
}

Ահա և վերջ։ Այսքանով կարողանում եմ գեներացնել տրված բազմությունների դեկարտյան արտադրյալը, որի ամեն մի տարրը ձևավորվում ու արտածվում է կոնֆիգուրացիոն ֆայլի տեսքով։

Պատահական կոնֆիգուրացիաների գեներացիա

Պատահական կոնֆիգուրացիայով ֆայլերի գեներացիայի համար ես ընտրել եմ հետևյալ մոտեցումը։ Պատահակա թվերի օգնությամբ գեներացնել մի պատահական ինդեքս։ Այդ ինդեքսի հիման վրա հաշվել կոնֆիգուրացիայի հերթական համարը։ Գեներացնել ֆայլ ըստ ինդեքսի, իսկ համարը հիշել։ Իտերացիայի հաջորդ քայլում ֆայլը գեներացնելուց առաջ համարը որոնել նախորդ քայլերում հիշված համարների ցուցակում։ Եթե համարը արդեն կա, ապա պետք է կատարել նոր իտերացիա։

Ստորև բերված է Common Lisp լեզվով իրականացումը։

(defparameter *params* '() "Պարամետրերի ցուցակն է")
(defparameter *powers* '() "Արժեքների բազմությունների քանակները")
(defparameter *factors* '() "Ինդեքսի հաշվման բազմանդամի գործակիցները")
(defparameter *passed* '() "Արդեն գեներացրած տարբերակների համարները")

(defmacro calculate-powers (prs)
  `(mapcar #'(lambda (e) (list-length (second e))) ,prs))
(defmacro calculate-factors (pws)
  `(append (cdr (maplist #'(lambda (x) (apply #'* x)) ,pws)) '(1)))

(defun create-config (inx)
  (mapcar #'(lambda (a b) (cons (car a) (nth b (cadr a))))
          *params* inx))

(defun print-config (config ix)
  (let ((name (format nil "config~d.cfg" ix)))
    (with-open-file (out name :direction :output :if-exists :supersede)
      (dolist (cl config)
        (format out "~a = ~a~%" (car cl) (cdr cl))))))

(defun generate-files (max-num)
(dotimes (k max-num)
  (let* ((tup (mapcar #'random *powers*))
         (num (apply #'+ (mapcar #'* *factors* tup))))
    (when (not (member num *passed*))
      (print-config (create-config tup) k)
      (push num *passed*)))))